# 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 $n$ 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($\mathrm{(}\mathrm{A}\mathrm{,}\mathrm{\u2aaf}\mathrm{,}\mathrm{n}\mathrm{)}$)

Input: List $A$ of $n$ elements

Output: $A$ sorted, such that $\u2aaf$ is a total order^{} over $A$

begin

for $i\leftarrow 2\mathrm{\mathbf{t}\mathbf{o}\mathbf{n}}$ do

HeapInsert$\mathrm{(}A\mathrm{,}\mathrm{\u2aaf}\mathrm{,}i\mathrm{-}\mathrm{1}\mathrm{,}A\mathbf{}\mathrm{[}i\mathrm{]}\mathrm{)}$

for $i\leftarrow n\mathrm{\mathbf{d}\mathbf{o}\mathbf{w}\mathbf{n}\mathbf{t}\mathbf{o}\U0001d7d0}$ do

$A[i-1]\leftarrow \mathrm{\mathbf{H}\mathbf{e}\mathbf{a}\mathbf{p}\mathbf{R}\mathbf{e}\mathbf{m}\mathbf{o}\mathbf{v}\mathbf{e}}(\mathbf{H},\mathbf{i},\u2aaf)$

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 $\mathcal{O}(\mathrm{log}i)$. Thus overall the heapsort algorithm is $\mathcal{O}(n\mathrm{log}n)$.

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 $\mathcal{O}(n\mathrm{log}n)$.
Given its simple implementation and reasonable performance, heapsort is ideal for quickly implementing a decent sorting algorithm.

Title | heapsort |
---|---|

Canonical name | Heapsort |

Date of creation | 2013-03-22 12:31:02 |

Last modified on | 2013-03-22 12:31:02 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 9 |

Author | mathcam (2727) |

Entry type | Algorithm |

Classification | msc 68P10 |

Related topic | HeapInsertionAlgorithm |

Related topic | HeapRemovalAlgorithm |

Related topic | Heap |

Related topic | SortingProblem |