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.
Input: List of elements
Output: sorted, such that is a total order over
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.
|Date of creation||2013-03-22 12:31:02|
|Last modified on||2013-03-22 12:31:02|
|Last modified by||mathcam (2727)|