Source of 27.11.java

Structures and functions

  1: // @author Frank M. Carrano, Timothy M. Henry
  2: // @version 5.0
  3: // Precondition: checkIntegrity has been called.
  4: private void reheap(int rootIndex)
  5: {
  6:    boolean done = false;
  7:    T orphan = heap[rootIndex];
  8:    int leftChildIndex = 2 * rootIndex;

 10:    while (!done && (leftChildIndex <= lastIndex) )
 11:    {
 12:       int largerChildIndex = leftChildIndex; // Assume larger
 13:       int rightChildIndex = leftChildIndex + 1;

 15:       if ( (rightChildIndex <= lastIndex) &&
 16:             heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0)
 17:       {
 18:          largerChildIndex = rightChildIndex;
 19:       } // end if

 21:       if (orphan.compareTo(heap[largerChildIndex]) < 0)
 22:       {
 23:          heap[rootIndex] = heap[largerChildIndex];
 24:          rootIndex = largerChildIndex;
 25:          leftChildIndex = 2 * rootIndex;
 26:       }
 27:       else
 28:          done = true;
 29:    } // end while

 31:    heap[rootIndex] = orphan;
 32: } // end reheap