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.
1 subtype index is positive range 1..N; 2 type sort_array is array(index) of integer; 3 4 procedure heapsort (arr: in out sort_array) 5 is 6 N: index := arr'LENGTH; 7 t: integer; 8 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; 33 34 begin 35 36 -- construct the heap 37 38 for k in reverse 1..N/2 loop 39 siftdown (N, k); 40 end loop; 41 42 -- remove elements in descending order 43 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 ]
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 ]