|
The heapsort algorithm is an elegant application of the heap data structure to the sorting problem. It consists of building a heap out of some list of  elements, and the removing a maximal value one at a time.
The following pseudocode illustrates the heapsort algorithm. It builds upon the heap insertion and heap removal algorithms.
Algorithm HEAPSORT(
 )
Input: List  of  elements
Output:  sorted, such that  is a total order over 
begin
![$\textstyle \parbox{\textwidth}{ \textbf{for} $i\gets2\bf{ to }n$\ \textbf{do}\\... ... \hspace*{0.4in}\parbox{\textwidth}{$A[i-1]\gets\bf{HeapRemove}(H,i,\preceq)$}}$](http://images.planetmath.org:8080/cache/objects/2755/l2h/img8.png "$\textstyle \parbox{\textwidth}{ \textbf{for} $i\gets2\bf{ to }n$\ \textbf{do}\\... ... \hspace*{0.4in}\parbox{\textwidth}{$A[i-1]\gets\bf{HeapRemove}(H,i,\preceq)$}}$")
end
Note that the algorithm given is based on a top-down heap insertion algorithm. It is possible to get better results through bottom-up heap construction.
Each step of each of the two for loops in this algorithm has a runtime complexity of
 . Thus overall the heapsort algorithm is
 .
Heapsort is not quite as fast as quicksort in general, but it is not much slower, either. Also, like quicksort, heapsort is an in-place sorting algorithm, but not a stable sorting algorithm. Unlike quicksort, its performance is guaranteed, so despite the ordering of its input its worst-case complexity is
 . Given its simple implementation and reasonable performance, heapsort is ideal for quickly implementing a decent sorting algorithm.
| 
