A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 819

reason. If we call percolateDown on nodes in reverse level order, then at the
point percolateDown(i) is processed, all descendants of node i will have been
processed by a prior call to percolateDown . This process leads to an incredibly
simple algorithm for buildHeap , which is shown in Figure 21.16. Note that
percolateDown need not be performed on a leaf. Thus we start at the highest
numbered nonleaf node.
The tree in Figure 21.17(a) is the unordered tree. The seven remaining
trees in Figures 21.17(b) through 21.20 show the result of each of the seven
percolateDown operations. Each dashed line corresponds to two comparisons:
one to find the smaller child and one to compare the smaller child with
the node. Notice that the ten dashed lines in the algorithm correspond to
20 comparisons. (There could have been an eleventh line.)

figure 21.15
Recursive view of the
heap

R

1 /**
2 * Establish heap order property from an arbitrary
3 * arrangement of items. Runs in linear time.
4 */
5 private void buildHeap( )
6 {
7 for( int i = currentSize / 2; i > 0; i-- )
8 percolateDown( i );
9 }

figure 21.16
Implementation of the
linear-time buildHeap
method

figure 21.17
(a) Initial heap;
(b) after
percolateDown(7)

92 92

47 21 47 21

20 12 45 63 20 12 45 63

61 17 55 37 25 64 83 73 61 17 55 37 25 64 83 73

(a) (b)