heapsort
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 Algorithm
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
for do
HeapInsert
for do
end
Analysis
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.