Java Reference
In-Depth Information
R
H1
H2
Figure5.21
Final stage in the heap-building algorithm. Both subtrees of node R
are heaps. All that remains is to push R down to its proper level in the heap.
1
7
7
5
7
5
1
5
6
4
2
6
3
4
2
6
3
4
2
1
3
(A)
(B)
(C)
Figure5.22
The siftdown operation. The subtrees of the root are assumed to
be heaps. (a) The partially completed heap. (b) Values 1 and 7 are swapped.
(c) Values 1 and 6 are swapped to form the final heap.
One good algorithm stems from induction. Suppose that the left and right sub-
trees of the root are already heaps, and R is the name of the element at the root.
This situation is illustrated by Figure 5.21. In this case there are two possibilities.
(1) R has a value greater than or equal to its two children. In this case, construction
is complete. (2) R has a value less than one or both of its children. In this case,
R should be exchanged with the child that has greater value. The result will be a
heap, except that R might still be less than one or both of its (new) children. In
this case, we simply continue the process of “pushing down” R until it reaches a
level where it is greater than its children, or is a leaf node. This process is imple-
mented by the private method
siftdown
. The siftdown operation is illustrated by
Figure 5.22.
This approach assumes that the subtrees are already heaps, suggesting that a
complete algorithm can be obtained by visiting the nodes in some order such that
the children of a node are visited before the node itself. One simple way to do this
is simply to work from the high index of the array to the low index. Actually, the
build process need not visit the leaf nodes (they can never move down because they
are already at the bottom), so the building algorithm can start in the middle of the
array, with the first internal node. The exchanges shown in Figure 5.20(b) result
from this process. Method
buildHeap
implements the building algorithm.
What is the cost of
buildHeap
? Clearly it is the sum of the costs for the calls
to
siftdown
. Each
siftdown
operation can cost at most the number of levels it
