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.)
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.
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 18 March 2019.
HTML page formatted Mon Mar 25 12:35:26 2019.
Cite this as:
Paul E. Black, "heapsort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 18 March 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/heapSort.html