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 node_{i} are node_{2i} and node_{2i+1}, and that conversely, the parent of a node_{i} is node_{iDIV2}, 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.

MODULEHSort; (* A simple demonstration of heap sorting by R. Sutcliffe modified 1996 10 22 *)FROMSTextIOIMPORTWriteLn, WriteChar;FROMSWholeIOIMPORTWriteCard;CONSTmax = 18;VARsource :ARRAY[1..max]OFCARDINAL; (* the array to sort *)PROCEDUREWriteArray; (* writes out the elements comma delimited *)VARcount :CARDINAL;BEGINFORcount := 1TOmaxDOWriteCard (source [count], 3);IFcount # maxTHENWriteChar (",");ELSEWriteLn;END;END;ENDWriteArray;PROCEDURESwap (VARone, two :CARDINAL); (* Exchange values in one and two. *)VARtemp :CARDINAL;BEGINtemp := one; one := two; two := temp;ENDSwap; (* 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 *)PROCEDURELeftChild (n :CARDINAL): CARDINAL; BEGINRETURN2 * n + 1;ENDLeftChild;PROCEDURERightChild (n :CARDINAL) :CARDINAL;BEGIN RETURN2 * n + 2;ENDRightChild;PROCEDURESiftDown (VARsource :ARRAYOFCARDINAL; 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. *)VARdata :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)])THENsource [node] := source [LeftChild (node)]; node := LeftChild (node);ELSEsource [node] := source [RightChild (node)]; node := RightChild (node);END;END; (* put data into proper place *) source [node] := data;ENDSiftDown;PROCEDUREHeapSort (VARsource:ARRAYOFCARDINAL; 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. *)VARcount :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)DIV2;WHILEcount > lBoundDODEC(count); SiftDown (source, count, uBound);END; (* while count *) (* Now de-heap smallest item to largest *) count := uBound;WHILEcount > lBoundDO(* 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 *)ENDHeapSort;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;ENDHSort.

In the method used, there are (n-1)/2 passes and up to nlog_{2}n 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)log_{2}n comparisons to produce a sorted tree. Thus, heap sorting is **O**(nlog_{2}n) 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.