Source of 27.19.java

Structures and functions

  1: // @author Frank M. Carrano, Timothy M. Henry
  2: // @version 5.0
  3: private static <T extends Comparable<? super T>>
  4:         void reheap(T[] heap, int rootIndex, int lastIndex)
  5: {
  6:    boolean done = false;
  7:    T orphan = heap[rootIndex];
  8:    int leftChildIndex = 2 * rootIndex + 1;

 10:    while (!done && (leftChildIndex <= lastIndex))
 11:    {
 12:       int largerChildIndex = leftChildIndex;
 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 + 1;
 26:       }
 27:       else
 28:          done = true;
 29:    } // end while

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