Java Reference
In-Depth Information
27 fixHeap(
0
, n);
28 }
29 }
30
31 /**
32
Ensures the heap property for a subtree, provided its
33
children already fulfill the heap property.
34 @param rootIndex
the index of the subtree to be fixed
35 @param lastIndex
the last valid index of the tree that
36
contains the subtree to be fixed
37 */
38
private void
fixHeap(
int
rootIndex,
int
lastIndex)
39 {
40
//
Remove root
41
int
rootValue = a[rootIndex];
42
43
//
Promote children while they are larger than the root
44
45
int
index = rootIndex;
46
boolean
more =
true
;
47
while
(more)
48 {
49
int
childIndex =
getLeftChildIndex(index);
50
if
(childIndex <= lastIndex)
51 {
52
//
Use right child instead if it is larger
53
int
rightChildIndex =
getRightChildIndex(index);
54
if
(rightChildIndex <= lastIndex
55 && a[rightChildIndex] >
a[childIndex])
56 {
57 childIndex = rightChildIndex;
58 }
59
60
if
(a[childIndex] > rootValue)
61 {
62
//
Promote child
63 a[index] = a[childIndex];
754
755
