Data Structures, Algorithms, & Applications in Java
Chapter 13, Exercise 33

A changeMin can be done by changing the root element and then performing a root to leaf scan of the min heap (as in a remove min) sliding elements up if they are smaller than the new element. The derived class has all the public member methods of MinHeap plus the method changeMin. The code for the derived class ExtendedMinHeap is given below. 

public class ExtendedMinHeap extends MinHeap
{
   // constructor
   public ExtendedMinHeap(int initialCapacity)
      {super(initialCapacity);}

   public ExtendedMinHeap()
      {super();}

   
   /** replace the current min element by theElement
     * @return original min element */
   public Comparable changeMin(Comparable theElement)
   {
      if (size == 0)
      {// heap is empty, heap capacity is at least 1
         heap[++size] = theElement;
         return null;
      }

      // save min element in e
      Comparable e = heap[1];
   
      // put replacement element into the heap
      int i = 1,                // location of vacancy
          ci = 2;               // ci is child of i
      while (ci <= size)
      {// find place to put theElement
         if (ci < size && heap[ci].compareTo(heap[ci + 1]) > 0)
            ci++;
         // now ci points to smaller child of i
   
         // can we put theElement in heap[i]?
         if (theElement.compareTo(heap[ci]) <= 0)
            break;              // yes
   
         // no
         heap[i] = heap[ci];    // move child up
    
         // move i and ci one level down
         i = ci;
         ci *= 2;
      }
   
      heap[i] = theElement;
      return e;
   }
}


With the availability of the changeMin method, the code for makeSchedule may be made more efficient. The new code is given below. The lines that have changed are shown in red. A test program and output appear in the files ImprovedLPTSchedule.*. 
public static void makeSchedule(JobNode [] a, int m)
{
   if (a.length <= m)
   {
      System.out.println("Schedule each job on a different machine.");
      return;
   }

   HeapSort.heapSort(a); // in ascending order

   // initialize m machines and the min heap
   ExtendedMinHeap machineHeap = new ExtendedMinHeap(m);
   for (int i = 1; i <= m; i++)
   {
      MachineNode x = new MachineNode(i, (Operable) a[1].time.zero());
      machineHeap.put(x);
   }

   // construct schedule
   for (int i = a.length - 1; i >= 1; i--)
   {// schedule job i on first free machine
      MachineNode x = (MachineNode) machineHeap.getMin();
      System.out.println("Schedule job " + a[i].id 
           + " on machine " + x.id + " from " + x.avail
           + " to " + x.avail.add(a[i].time));
      x.avail.increment(a[i].time);  // new available time for this machine
      machineHeap.changeMin(x);
   }
}