File:Sorting_heapsort_anim.gif · Wikimedia Commons · See Wikimedia Commons
heapsort
Sign in to saveIn computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that heap, placing it at the end of the array in a similar manner to Selection sort.
Key facts
- Algorithm.caption
- A run of heapsort sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
- Algorithm.data
- Array
- Algorithm.time
- O(n\log n)
- Algorithm.average time
- O(n\log n)
- Algorithm.best time
- O(n\log n) (distinct keys)or O(n) (equal keys)
- Algorithm.space
- O(n) total O(1) auxiliary
- Algorithm.class
- Sorting algorithm
- Algorithm.image
- File:Sorting heapsort anim.gif
via Wikipedia infobox
Wikidata facts
- Image
- Binary heap bottomup vs topdown.svg
Show 2 more facts
- time of discovery or invention
- 1964-00-00
- Commons category
- Heap sort
Sources (2)
via Wikidata · CC0
~20 min read
Article
16 sectionsContents
- Overview
- Algorithm
- Pseudocode
- Standard implementation
- Variations
- Williams' heap construction
- Bottom-up heapsort
- Other variations
- Comparison with other sorts
- Example
- Heap construction (Williams' algorithm)
- Heap construction (Floyd's algorithm)
- Heap extraction
- Notes
- References
- External links
In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that heap, placing it at the end of the array in a similar manner to Selection sort.
Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantages of very simple implementation and a more favorable worst-case runtime. Most real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate. Heapsort is an in-place algorithm, but it is not a stable sort.