Source of 26.11.java

Structures and functions

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