Advanced Data Structures - Java Concepts - page 1019

73 private void fixHeap()
74 {
75 Comparable root = elements.get( 1 );
76
77 int lastIndex = elements.size() - 1 ;
78 // Promote children of removed root while they are larger
than last
79
80 int index = 1 ;
81 boolean more = true ;
82 while (more)
83 {
84 int childIndex =
getLeftChildIndex(index);
85 if (childIndex <= lastIndex)
86 {
87 // Get smaller child
88
89 // Get left child first
90 Comparable child =
getLeftChild(index);
91
92 // Use right child instead if it is smaller
93 if (getRightChildIndex(index) <=
lastIndex
94 &&
getRightChild(index).compareTo(child) < 0 )
95 {
96 childIndex =
getRightChildIndex(index);
97 child = getRightChild(index);
98 }
99
100 // Check if larger child is smaller than root
101 if (child.compareTo(root) < 0 )
102 {
103 // Promote child
104 elements.set(index, child);
105 index = childIndex;
106 }
107 else
108 {

747
748