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

public class MaxHeapWithMinAndMaxElements implements MaxPriorityQueue
{
   // data members
   Comparable [] heap;      // array for complete binary tree
   int size;                // number of elements in heap
   Comparable minElement;   // all elements must be >= minElement
   Comparable maxElement;   // all elements must be <= maxElement

   // constructors
   /** create a heap with the given initial capacity */
   public MaxHeapWithMinAndMaxElements(int initialCapacity,
                 Comparable theMinElement, Comparable theMaxElement)
   {
      if (initialCapacity < 1)
         throw new IllegalArgumentException
                   ("initialCapacity must be >= 1");
      heap = new Comparable [2 * (initialCapacity + 1)];
      size = 0;
      maxElement = theMaxElement;
      minElement = theMinElement;

      // put maxElement in heap[0]
      heap[0] = maxElement;

      // put minElement in all other positions
      for (int i = 1; i < heap.length; i++)
         heap[i] = minElement;
   }
   
   /** create a heap with initial capacity 10 */
   public MaxHeapWithMinAndMaxElements(Comparable theMinElement,
                                       Comparable theMaxElement)
      {this(10, theMinElement, theMaxElement);}

   // methods
   /** @return true iff the heap is empty */
   public boolean isEmpty()
      {return size == 0;}

   /** @return number of elements in the heap */
   public int size()
      {return size;}

   /** @return maximum element
     * @return null if the heap is empty */
   public Comparable getMax()
   {
      if (size == 0)
         return null;
      else
         return heap[1];
   }

   /** put theElement into the heap */
   public void put(Comparable theElement)
   {
      // validate new element
      if (theElement.compareTo(minElement) < 0 ||
          theElement.compareTo(maxElement) > 0)
         throw new IllegalArgumentException
               ("element must be within specified range");

      // increase array size if necessary
      if (size == heap.length / 2 - 1)
      {// double array size and fill new positions with minElement
         int oldLength = heap.length;
         heap = (Comparable []) ChangeArrayLength.changeLength1D
                                    (heap, 2 * heap.length);
         for (int i = oldLength; i < heap.length; i++)
            heap[i] = minElement;
      }

   
      // find place for theElement
      // i starts at new leaf and moves up tree
      int i = ++size;
      // no need to check if root reached
      // because heap[0] = MaxElement
      while (heap[i / 2].compareTo(theElement) < 0)
      {
         // cannot put theElement in heap[i]
         heap[i] = heap[i / 2]; // move element down
         i /= 2;                // move to parent
      }
   
      heap[i] = theElement;
   }
   
   /** 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
   
      // replace with minElement
      heap[size--] = minElement;
   
      // first propagate vacancy 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
         // no need to check if ci < size
         // because heap[size] has minElement
         if (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 heap[i], start from here and insert y
      // no need to check if root reached
      // because heap[0] = maxElement
      while (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;
   }
   
   /** initialize max heap to element array theHeap */
   public void initialize(Comparable [] theHeap, int theSize)
   {
      heap = theHeap;
      size = theSize;
   
      if (2 * (size + 1) < heap.length)
         // double array size
         heap = (Comparable []) ChangeArrayLength.changeLength1D
                                    (heap, 2 * heap.length);

      // fill unused positions with minElement
      for (int i = size + 1; i < heap.length; i++)
         heap[i] = minElement;

      // put maxElement into heap[0]
      heap[0] = maxElement;

      // make into a max heap by running old method as
      // we do not expect to propagate all the way down
      for (int i = size / 2; i >= 1; i--)
      {
         Comparable y = heap[i]; // root of subtree
   
         // find place to put y
         int c = 2 * i; // parent of c is target
                        // location for y
         while (c <= size)
         {
            // heap[c] should be larger sibling
            // no need to check if c < size as
            // all unused spots have minElement
            if (heap[c].compareTo(heap[c + 1]) < 0)
               c++;
   
            // can we put y in heap[c/2]?
            if (y.compareTo(heap[c]) >= 0)
               break;  // yes
   
            // no
            heap[c / 2] = heap[c]; // move child up
            c *= 2;                // move down a level
         }
         heap[c / 2] = y;
      }
   }
}

public class NewHeapSort
{
   /** sort the elements a[1 : a.length - 1] using
     * the heap sort method */
   public static void heapSort(Comparable [] a)
   {
      if (a.length <= 2)
         // array has fewer than two elements
         return;

      // more than 1 element, first find min and max elements
      Comparable min = a[1];
      Comparable max = a[1];
      for (int i = 2; i < a.length; i++)
         if (min.compareTo(a[i]) > 0)
            min = a[i];
         else
            if (max.compareTo(a[i]) < 0)
               max = a[i];
   
      // create a max heap of the elements
      MaxHeapWithMinAndMaxElements h =
             new MaxHeapWithMinAndMaxElements(1, min, max);
      h.initialize(a, a.length - 1);
   
      // extract one by one from the max heap
      for (int i = a.length - 1; i >= 1; i--)
         a[i] = h.removeMax();
        
   }
}