Statements (28)
Predicate | Object |
---|---|
gptkbp:instanceOf |
Sorting algorithm
|
gptkbp:alternativeTo |
Merge sort
Quick sort |
gptkbp:average_case_performance |
O(n log n)
|
gptkbp:best_case_performance |
O(n log n)
|
gptkbp:canBe |
Priority queue
|
gptkbp:category |
Comparison sort
|
gptkbp:external_sort |
No
|
gptkbp:first_step |
Build a max heap
|
https://www.w3.org/2000/01/rdf-schema#label |
Heap sort
|
gptkbp:internal_sort |
Yes
|
gptkbp:introduced |
gptkb:J._W._J._Williams
|
gptkbp:introducedIn |
1964
|
gptkbp:is_in-place |
Yes
|
gptkbp:is_recursive |
No (typically implemented iteratively)
|
gptkbp:is_stable |
No
|
gptkbp:not_stable |
Yes
|
gptkbp:second_step |
Extract maximum repeatedly
|
gptkbp:spaceComplexity |
O(1)
|
gptkbp:time_complexity_(average_case) |
O(n log n)
|
gptkbp:time_complexity_(best_case) |
O(n log n)
|
gptkbp:time_complexity_(worst_case) |
O(n log n)
|
gptkbp:used_in |
Computer science
|
gptkbp:uses |
Binary heap
|
gptkbp:uses_data_structure |
gptkb:Heap
|
gptkbp:worst_case_performance |
O(n log n)
|
gptkbp:bfsParent |
gptkb:Heap
|
gptkbp:bfsLayer |
6
|