NIST

heapsort

(algorithm)

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 ...)
in-place sort.

Specialization (... is a kind of me.)
adaptive heap sort, smoothsort.

Aggregate child (... is a part of or used in me.)
build-heap, heap.

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.

Author: PEB

Implementation

Prof. Dr. Hans Wener Lang's definitions, explanations, diagrams, and pseudo-code (Java), Bro. David Carlson's heaps and heapsort tutorial and code (C++). Paulo Roma's (Pascal) implementation. Worst-case behavior annotated for real time (WOOP/ADA), including bibliography.

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 10 February 2020.
HTML page formatted Mon Feb 10 09:29:05 2020.

Cite this as:
Paul E. Black, "heapsort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 10 February 2020. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/heapSort.html