Definition: A sort algorithm that builds a heap, then repeatedly extracts the maximum item. Run time is O(n log n).
Generalization (I am a kind of ...)
Specialization (... is a kind of me.)
adaptive heap sort, smoothsort.
Aggregate child (... is a part of or used in me.)
build-heap, heap, sift up.
See also selection sort.
Note: Heapsort can be seen as a variant of selection sort in which sorted items are arranged (in a heap) to quickly find the next item.
Some times called "tournament sort" by analogy between a heap, with its heap property, and a tree of matches in a sports tournament.
Comparison of quicksort, heapsort, and merge sort on modern processors.
An illustration of heap sort followed by a race between heap sort and merge sort.
Robert W. Floyd, Algorithm 245 Treesort 3, CACM, 7(12):701, December 1964.
J. W. J. Williams, Algorithm 232 Heapsort, CACM, 7(6):378-348, June 1964.
Although Williams clearly stated the idea of heapsort, Floyd gave a complete, efficient implementation nearly identical to what we use today.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 6 April 2023.
HTML page formatted Fri Apr 7 09:27:46 2023.
Cite this as:
Paul E. Black, "heapsort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 April 2023. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/heapSort.html