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

The new code for removeMax is given below. It is expected to run faster than the old code when the cost of comparing two elements is high. A test program and output appear in the files NewMaxHeap.*. 
public class NewMaxHeap extends MaxHeap
{
   // constructors
   /** create a heap with the given initial capacity */
   public NewMaxHeap(int initialCapacity)
      {super(initialCapacity);}
   
   /** create a heap with initial capacity 10 */
   public NewMaxHeap()
      {super(10);}

   // override MaxHeap.removeMax
   /** remove max element and return it */
   public Comparable removeMax()
   {
      // if heap is empty return null
      if (size == 0) return null;       // heap empty
   
      Comparable x = heap[1];           // max element
   
      // restucture heap
      Comparable y = heap[size--];      // last element
   
      // first propagate vacancy from root to a leaf
      int i = 1,                        // current position of vacancy
          ci = 2;                       // child of i
      while (ci <= size)
      {
         // heap[ci] should be larger child of i
         if (ci < size && heap[ci].compareTo(heap[ci+ 1]) < 0)
            ci++;
   
         // move larger child to heap[i]
         heap[i] = heap[ci];            // move child up
         i = ci;                        // move down a level
         ci *= 2;
      }
   
      i = ci / 2;
      // vacancy is now at the leaf heap[i], start from here and insert y
      while (i != 1 && y.compareTo(heap[i / 2]) > 0)
      {// cannot put y in heap[i]
         heap[i] = heap[i / 2];         // move element down
         i /= 2;                        // move to parent
      }
   
      heap[i] = y;
   
      return x;
   }
}