Java Reference
In-Depth Information
ȒFixing the heapȓ operates on a binary tree whose child trees are heaps but whose
root value may not be smaller than the descendants. The procedure turns the tree into
a heap, by repeatedly promoting the smallest child value, moving the root value to its
proper location.
Of course, we cannot simply apply this procedure to the initial sequence of unsorted
valuesȌthe child trees of the root are not likely to be heaps. But we can first fix small
subtrees into heaps, then fix larger trees. Because trees of size 1 are automatically
heaps, we can begin the fixing procedure with the subtrees whose roots are located in
the next-to-lowest level of the tree.
The sorting algorithm uses a generalized
fixHeap
method that fixes a subtree with a
given root index:
void fixHeap(int rootIndex, int lastIndex)
751
