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

1 /**
2 * Internal method to percolate down in the heap.
3 * @param hole the index at which the percolate begins.
4 */
5 private void percolateDown( int hole )
6 {
7 int child;
8 AnyType tmp = array[ hole ];
9
10 for( ; hole * 2 <= currentSize; hole = child )
11 {
12 child = hole * 2;
13 if( child != currentSize &&
14 compare( array[ child + 1 ], array[ child ] ) < 0 )
15 child++;
16 if( compare( array[ child ], tmp ) < 0 )
17 array[ hole ] = array[ child ];
18 else
19 break;
20 }
21 array[ hole ] = tmp;
22 }

figure 21.14
The percolateDown method used for remove and buildHeap

the buildHeap operation:
linear-time heap construction

21.3

The buildHeap operation takes a complete tree that does not have heap order
and reinstates it. We want it to be a linear-time operation, since N insertions
could be done in O ( N log N ) time. We expect that O ( N ) is attainable because
N successive insertions take a total of O ( N ) time on average, based on the
result stated at the end of Section 21.2.1. The N successive insertions do more
work than we require because they maintain heap order after every insertion
and we need heap order only at one instant.
The easiest abstract solution is obtained by viewing the heap as a recur-
sively defined structure, as shown in Figure 21.15: We recursively call
buildHeap on the left and right subheaps. At that point, we are guaranteed that
heap order has been established everywhere except at the root. We can
establish heap order everywhere by calling percolateDown for the root. The
recursive routine works by guaranteeing that when we apply percolateDown(i) ,
all descendants of i have been processed recursively by their own calls to
percolateDown . The recursion, however, is not necessary, for the following

The buildHeap oper-
ation can be done
in linear time by
applying a perco-
late down routine to
nodes in reverse
level order.