Source of 26.19.java

Structures and functions

  1: private static <T extends Comparable<? super T>>
  2:         void reheap(T[] heap, int rootIndex, int lastIndex)
  3: {
  4:    boolean done = false;
  5:    T orphan = heap[rootIndex];
  6:    int leftChildIndex = 2 * rootIndex + 1;
  7: 
  8:    while (!done && (leftChildIndex <= lastIndex))
  9:    {
 10:       int largerChildIndex = leftChildIndex;
 11:       int rightChildIndex = leftChildIndex + 1;
 12: 
 13:       if ( (rightChildIndex <= lastIndex) &&
 14:             heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0)
 15:       {
 16:          largerChildIndex = rightChildIndex;
 17:       } // end if
 18: 
 19:       if (orphan.compareTo(heap[largerChildIndex]) < 0)
 20:       {
 21:          heap[rootIndex] = heap[largerChildIndex];
 22:          rootIndex = largerChildIndex;
 23:          leftChildIndex = 2 * rootIndex + 1;
 24:       }
 25:       else
 26:          done = true;
 27:    } // end while
 28: 
 29:    heap[rootIndex] = orphan;
 30: } // end reheap
 31: // Version 4.0