## You are here

Homeheapsort

## Primary tabs

# 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($(A,\preceq,n)$)

Input: List $A$ of $n$ elements

Output: $A$ sorted, such that $\preceq$ is a total order over $A$

begin

for $i\leftarrow 2\bf{to}n$ do

HeapInsert$(A,\preceq,i-1,A[i])$

for $i\leftarrow n\bf{downto}2$ do

$A[i-1]\leftarrow\bf{HeapRemove}(H,i,\preceq)$

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

## Mathematics Subject Classification

68P10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## See balanced binary tree

Initially this entry confused me. I kept

wondering, "Where are the parent/child links?"

I didn't quite grok this till I remembered that a

heap is a balanced binary tree, and as such can

be represented by an array. So entry 0 is the

parent of entries 1,2 which in turn are the parents

of entries 3,4 and 5,6 respectively, etc.

The problem, I guess, is that "balanced binary tree"

is two clicks away from "heapsort", and I missed

this vital bit of information on the first pass

over the material