Heap Sort

Algorithm description

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.

Algorithm implementation

 1  subtype index is positive range 1..N;
 2  type sort_array is array(index) of integer;
 4  procedure heapsort (arr: in out sort_array)
 5  is
 6      N: index := arr'LENGTH;
 7      t: integer;
 9      procedure siftdown (N, k: index)
10      is
11          j: index;
12          v: integer;
13          w: integer;
14      begin
15          v := arr(k); w := k;
16          discrete h := k in 1..N/2
17              new h := 2*h | 2*h+1
18          loop
19              j := 2*h;
20              if j < N and then arr(j) < arr(j+1) then
21                  j := j+1;
22              end if;
23              if v >= arr(j) then
24                  w := h;  -- save h for writing back (line 31)
25                  exit;
26              end if;
27              arr(h) := arr(j);
28              h := j;
29              w := h;  -- save h for writing back (line 31)
30          end loop;
31          arr(w) := v;
32      end siftdown;
34  begin
36      -- construct the heap
38      for k in reverse 1..N/2 loop
39          siftdown (N, k);
40      end loop;
42      -- remove elements in descending order
44      for M in reverse 2..N loop
45          t := arr(1);
46          arr(1) := arr(M);
47          arr(M) := t;
48          siftdown ((M-1), 1);
49      end loop;
50  end heapsort;

[ Sourcefile ]

Notes on design

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.

Worst Case Performance

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.

Selected Bibliography

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

[ Samples Overview | Bibliography | WOOP Project ]