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.
demonstration. 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 E. Black.
Entry modified 25 January 2010.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "heapsort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 25 January 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/heapSort.html