Java Reference
In-Depth Information
753
Here, lastIndex is the index of the last node in the full tree. The fixHeap
method needs to be invoked on all subtrees whose roots are in the next-to-last level.
Then the subtrees whose roots are in the next level above are fixed, and so on.
Finally, the fixup is applied to the root node, and the tree is turned into a heap (see
Figure 21 ).
That repetition can be programmed easily. Start with the last node on the
next-to-lowest level and work toward the left. Then go to the next higher level. The
node index values then simply run backwards from the index of the last node to the
index of the root.
int n = a.length - 1;
for (int i = (n - 1) / 2; i >= 0; i--)
fixHeap(i, n);
Note that the loop ends with index 0. When working with a given array, we don't have
the luxury of skipping the 0 entry. We consider the 0 entry the root and adjust the
formulas for computing the child and parent index values.
After the array has been turned into a heap, we repeatedly remove the root element.
Recall from the preceding section that removing the root element is achieved by
placing the last element of the tree in the root and calling the fixHeap method.
Rather than moving the root element into a separate array, we will swap the root
element with the last element of the tree and then reduce the tree length. Thus, the
removed root ends up in the last position of the array, which is no longer needed by
the heap. In this way, we can use the same array both to hold the heap (which gets
shorter with each step) and the sorted sequence (which gets longer with each step).
There is just a minor inconvenience. When we use a min-heap, the sorted sequence is
accumulated in reverse order, with the smallest element at the end of the array. We
could reverse the sequence after sorting is complete. However, it is easier to use a
max-heap rather than a min-heap in the heapsort algorithm. With this modification,
the largest value is placed at the end of the array after the first step. After the next
step, the next-largest value is swapped from the heap root to the second position from
the end, and so on (see Figure 22 ).
The following class implements the heapsort algorithm.
Search WWH ::




Custom Search