In the tree implementation of the heap, both binary tree pointers and linear pointers were employed so as to diversify the traversability of the tree. However, if it is noted that when the nodes are numbered in row order, the children of a nodei are node2i and node2i+1, and that conversely, the parent of a nodei is nodeiDIV2, it becomes apparent that the tree structure is not required for the implementation, and that an array could be used instead. The advantage of using an array is that items can be randomly accessed by their node number, and the necessity for all the linkage is removed. However, the linkage does allow for efficient binary type searches in the tree, so the advantage is not all to the array implementation.
However, there is an exception to this even handed discussion, and it arises from the observation that it is possible to use a heap to generate sorted data. Consider some data that is already in a heap. By virtue of this, the root is the smallest item. Swap it with the last item, mark it as "sorted" and sift the new root down the smaller branch (but not into the sorted part) until it is again a proper child. The root is now the second largest item. Repeat the above process, swapping with the second last item. If we trace this with a seven item heap, and mark the sorted items in bold, the steps are:
The largest item is now at the root, and the tree can now be traversed in reverse row order to visit the items from least to greatest. The structure is now both sorted and is a reverse (inverted) heap. All this could be implemented and added to the tree implementation shown above, or it could be implemented as a sorting routine acting on arrays in the same manner as the ones in Chapter 13.
In the simple array implementation of the heapsort that follows, the parameters of the heapsort procedure are the same as in earlier sorting routines. The array is heapified by starting at the middle element and working back to the first element, sifting down as one goes. It is then sorted by the method outlined above.
MODULE HSort;
(* A simple demonstration of heap sorting
by R. Sutcliffe
modified 1996 10 22 *)
FROM STextIO IMPORT
WriteLn, WriteChar;
FROM SWholeIO IMPORT
WriteCard;
CONST
max = 18;
VAR
source : ARRAY [1..max] OF CARDINAL; (* the array to sort *)
PROCEDURE WriteArray;
(* writes out the elements comma delimited *)
VAR
count : CARDINAL;
BEGIN
FOR count := 1 TO max
DO
WriteCard (source [count], 3);
IF count # max
THEN
WriteChar (",");
ELSE
WriteLn;
END;
END;
END WriteArray;
PROCEDURE Swap (VAR one, two : CARDINAL);
(* Exchange values in one and two. *)
VAR
temp : CARDINAL;
BEGIN
temp := one; one := two; two := temp;
END Swap;
(* Since arrays to sort are open, they are numbered from 0.. n-1, so the child functions have to be altered from the way in which they are defined to add one to the index *)
PROCEDURE LeftChild (n : CARDINAL) : CARDINAL;
BEGIN
RETURN 2 * n + 1;
END LeftChild;
PROCEDURE RightChild (n : CARDINAL) : CARDINAL;
BEGIN
RETURN 2 * n + 2;
END RightChild;
PROCEDURE SiftDown (VAR source : ARRAY OF CARDINAL; node, end : CARDINAL);
(* Sift data item down through heap until it is a proper child. If it is already in the right place, nothing happens. *)
VAR
data : CARDINAL;
BEGIN
(* set data item from node aside *)
data := source [node];
(* see if it needs to go down the tree *)
WHILE ((LeftChild (node) <= end) AND
( data > source [LeftChild (node)]))
OR ((RightChild (node) <= end) AND (data > source [RightChild (node)]))
DO (* pull up smaller child until it is a proper child *)
(* yes, so move smaller child up and look lower *)
IF (RightChild (node) > end)
OR (source [LeftChild (node)] <= source [RightChild (node)])
THEN
source [node] := source [LeftChild (node)];
node := LeftChild (node);
ELSE
source [node] := source [RightChild (node)];
node := RightChild (node);
END;
END;
(* put data into proper place *)
source [node] := data;
END SiftDown;
PROCEDURE HeapSort (VAR source: ARRAY OF CARDINAL;
lBound, uBound : CARDINAL);
(* The heapsort is a two step proccess. First, the data are put in a heap, and then the data is de-heaped in reverse sorted order. *)
VAR
count : CARDINAL;
BEGIN
(* Construct the inital heap. *)
(* We do this by starting at the last item that has a child and sifting down, then backing up toward the top one step at a time and repeating. *)
IF (uBound <= HIGH (source)) AND (uBound > lBound)
THEN
(* find where to start in the middle *)
count := (lBound + uBound + 1) DIV 2;
WHILE count > lBound
DO
DEC (count);
SiftDown (source, count, uBound);
END; (* while count *)
(* Now de-heap smallest item to largest *)
count := uBound;
WHILE count > lBound
DO
(* swap the smallest into the last position *)
Swap (source[lBound],source[count]);
DEC (count);
(* and sift the one swapped down to restore the heap up to one item short of the current last position *)
SiftDown (source, lBound, count);
END; (* while count *)
END; (* if *)
END HeapSort;
BEGIN
(* set up a little test *)
source [1] := 23; source [2] := 6; source [3] := 17;
source [4] := 32; source [5] := 13; source [6] := 67;
source [7] := 89; source [8] := 43; source [9] := 99;
source [10] := 56; source [11] := 32; source [12] := 83;
source [13] := 26; source [14] := 16; source [15] := 41;
source [16] := 98; source [17] := 34; source [18] := 77;
WriteArray;
HeapSort (source, 0, max-1);
WriteArray;
END HSort.
In the method used, there are (n-1)/2 passes and up to nlog2n comparisons on each pass to make the heap in the first place. Then, there are (n-2) passes with an average of up to (n/2)log2n comparisons to produce a sorted tree. Thus, heap sorting is O(nlog2n) and so is classified as an advanced sort. The reason it was not take up in the chapter on sorting is that one has to be able to appreciate what a tree arranged like a heap is in order to follow the algorithm, even though it is often implemented on arrays as it is in this section.
A priority queue is a queue in which every data item has a priority. Enqueing is done according to the priority, and dequeing is done in the normal manner. Conceptually, there is still a single linear structure (a lineup) into which items are inserted according to their priority. Items are then served from the front of the line.
The heap makes an ideal base from which to implement a priority queue. Enqueing can be done as e3nheaping, using the priority as the key field (highest on top of the heap). Dequeing is accomplished by serving from the top (root) of the heap, then promoting the highest priority of the two descendents of the root, repeating recursively until a leaf node is reached, and then deleting the leaf node using the portion heap delete function that follows a find. If one takes the reverse sorted heap from the first part of this section, thinks about the values now as priorities, and then does a serve, these steps are:
As this is a reverse sorted heap, the node with priority 19 does not move when sift up is called.
A complete implementation is not shown here, but is left as an exercise for the reader.