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, 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.

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. (Python). Worst-case behavior annotated for real time (WOOP/ADA), including bibliography.

More information

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.

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 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