Heapsort is an elegant and efficient sorting method defined from the basic operations on heaps. The idea is simply to build a heap containing the elements to be sorted and then to remove them all in order.

1subtypeindexispositiverange1..N;2typesort_arrayisarray(index)ofinteger;34procedureheapsort (arr:inoutsort_array)5is6N: index := arr'LENGTH;7t: integer;89proceduresiftdown (N, k: index)10is11j: index;12v: integer;13w: integer;14begin15v := arr(k); w := k;16discreteh := kin1..N/217newh := 2*h | 2*h+118loop19j := 2*h;20ifj < Nandthenarr(j) < arr(j+1)then21j := j+1;22endif;23ifv >= arr(j)then24w := h;-- save h for writing back (line 31)25exit;26endif;27arr(h) := arr(j);28h := j;29w := h;-- save h for writing back (line 31)30endloop;31arr(w) := v;32endsiftdown;3334begin3536-- construct the heap3738forkinreverse1..N/2loop39siftdown (N, k);40endloop;4142-- remove elements in descending order4344forMinreverse2..Nloop45t := arr(1);46arr(1) := arr(M);47arr(M) := t;48siftdown ((M-1), 1);49endloop;50endheapsort;

[ Sourcefile ]

The first for-loop *(lines 38 to 40)* constructs the heap
bottom up. This method views every position in the array as the
root of a small heap and takes advantage of the fact that
*siftdown* will work as well for such small heaps as for
the big heap. (There's no need to do anything with the heaps of
size 1 so the scan starts halfway back through the array.)

In the second for-loop *(lines 44 to 49)*, the largest
node (at heap position 1) is removed from the heap by exchanging
the first and last elements and calling *siftdown* for
this new first element of the remaining heap.

The procedure *siftdown* moves down the heap, exchanging the node
at position *k* with the larger of its two children if
necessary and stopping when the node at *k* is larger than both
children or the bottom is reached. A monotonical discrete loop is
absolutely suitable for sifting down the heap, because the loop-variable
takes always one of the children's positions in the heap (`2*h`
or `2*h+1`) for the next iteration.

Heapsort is of practical interest, because the number of steps
required to sort *N* elements is *guaranteed* to be
proportional to

**N log N**.

Unlike other sorting algorithms, there is no worst case input that makes Heapsort run slower. A detailed computation of the complexity of the above algorithm can be found in the paper Discrete Loops And Worst Case Performance, section 3.2.1.

[Bli94, section 3.2.1] [Ott93, p. 113] [Sed88, p. 153]

[ Samples Overview | Bibliography | WOOP Project ]