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

Lang's definitions, explanations, diagrams, Java applet, and pseudo-code (C), (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, (Rexx).

More information

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.

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 25 January 2010.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "heapsort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 25 January 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/heapSort.html