Heapsort
E459516
Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements in-place with O(n log n) time complexity and O(1) auxiliary space.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Floyd’s algorithm for heap construction | 1 |
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
comparison-based algorithm
ⓘ
in-place algorithm ⓘ sorting algorithm ⓘ |
| averageCasePerformanceComparedToQuicksort | often slower in practice ⓘ |
| basedOn |
binary tree
ⓘ
heap data structure ⓘ |
| cacheFriendliness | moderate ⓘ |
| canBeImplementedIteratively | true ⓘ |
| canBeImplementedRecursively | true ⓘ |
| category |
comparison sort
ⓘ
selection-based sort ⓘ |
| extractionPerElementTime | O(log n) ⓘ |
| hasPhase |
heap construction
ⓘ
repeated extraction ⓘ |
| heapConstructionTime | O(n) ⓘ |
| introducedBy | J. W. J. Williams NERFINISHED ⓘ |
| isComparisonSort | true ⓘ |
| isInPlace | true ⓘ |
| isStable | false ⓘ |
| numberOfComparisonsWorstCase | O(n log n) ⓘ |
| numberOfSwapsWorstCase | O(n log n) ⓘ |
| outputOrderForMaxHeap | ascending ⓘ |
| outputOrderForMinHeap | descending ⓘ |
| primaryOperation |
heapify
ⓘ
sift-down ⓘ |
| relatedAlgorithm |
Mergesort
NERFINISHED
ⓘ
Quicksort NERFINISHED ⓘ Selection sort ⓘ |
| relatedDataStructure | binary heap ⓘ |
| requiresRandomAccess | true ⓘ |
| sortingOrderSupport |
ascending
ⓘ
descending ⓘ |
| spaceComplexityAuxiliary | O(1) ⓘ |
| suitableForLinkedLists | false ⓘ |
| supportsOnlineSorting | false ⓘ |
| supportsRandomAccessArray | true ⓘ |
| timeComplexityWorstCase | O(n log n) ⓘ |
| typicalImplementationLanguageFeature | arrays ⓘ |
| usedIn | systems where worst-case guarantees are important ⓘ |
| usesDataStructure | binary heap ⓘ |
| usesHeapProperty |
max-heap
ⓘ
min-heap ⓘ |
| worksOn |
array of comparable elements
ⓘ
array of keys ⓘ |
| worstCasePerformanceComparedToQuicksort | better or equal ⓘ |
| yearIntroduced | 1964 ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
Robert W. Floyd
this entity surface form:
Floyd’s algorithm for heap construction