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

(a)

The modified ADT is:

---

AbstractDataType MaxPriorityQueueWithKey
{
   instances
      finite collection of elements, each has a priority or key

   operations
      isEmpty(): return true iff the queue is empty
      size() : return number of elements in the queue
      getMax(): return element with maximum priority or key
      put(theKey, theElement): insert theElement whose key is theKey
                               into the queue
     removeMax(): remove the element with largest priority from the queue and
                  return this element;
}

---

(b)

The corresponding Java interface is:

---

public interface MaxPriorityQueueWithKey
{
   public boolean isEmpty();
   public int size();
   public Object getMax();
   public void put(Comparable theKey, Object theObject);
   public Object removeMax();
}

---

(c)

The class MaxHeapWithKey, which is given below implements the above interface.

---

public class MaxHeapWithKey implements MaxPriorityQueueWithKey
{
   // top-level nested class
   public static class HeapElement
   {
      // data members
      Comparable key;
      Object element;

      // constructors
      public HeapElement() {}
     
      public HeapElement(Comparable theKey, Object theElement)
      {
         key = theKey;
         element = theElement;
      }

      public String toString()
         {return element.toString();}
   }

   // data members of MaxHeapWithKey
   HeapElement [] heap;   // array for complete binary tree
   int size;              // number of elements in heap

   // constructors
   /** create a heap with the given initial capacity */
   public MaxHeapWithKey(int initialCapacity)
   {
      if (initialCapacity < 1)
         throw new IllegalArgumentException
                   ("initialCapacity must be >= 1");
      heap = new HeapElement [initialCapacity + 1];
      size = 0;
   }
   
   /** create a heap with initial capacity 10 */
   public MaxHeapWithKey()
      {this(10);}

   // 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 Object getMax()
   {
      if (size == 0)
         return null;
      else
         return heap[1].element;
   }

   /** put theElement into the heap */
   public void put(Comparable theKey, Object theElement)
   {
      // increase array size if necessary
      if (size == heap.length - 1)
         heap = (HeapElement []) ChangeArrayLength.changeLength1D
                                    (heap, 2 * heap.length);
   
      // find place for theElement
      // i starts at new leaf and moves up tree
      int i = ++size;
      while (i != 1 && heap[i / 2].key.compareTo(theKey) < 0)
      {
         // cannot put theElement in heap[i]
         heap[i] = heap[i / 2]; // move element down
         i /= 2;                // move to parent
      }
   
      heap[i] = new HeapElement(theKey, theElement);
   }
   
   /** remove max element and return it */
   public Object removeMax()
   {
      // if heap is empty return null
      if (size == 0) return null;       // heap empty
   
      Object x = heap[1].element;       // max element
   
      // restucture heap
      HeapElement y = heap[size--];     // last element
   
      // find place for y starting at root
      int i = 1,  // current node of heap
          ci = 2; // child of i
      while (ci <= size)
      {
         // heap[ci] should be larger child of i
         if (ci < size &&
             heap[ci].key.compareTo(heap[ci + 1].key) < 0)
                ci++;
   
         // can we put y in heap[i]?
         if (y.key.compareTo(heap[ci].key) >= 0)
            break;   // yes
   
         // no
         heap[i] = heap[ci]; // move child up
         i = ci;             // move down a level
         ci *= 2;
      }
      heap[i] = y;
   
      return x;
   }
   
   /** initialize max heap to element array theHeap */
   public void initialize(HeapElement [] theHeap, int theSize)
   {
      heap = theHeap;
      size = theSize;
   
      // make into a max heap
      for (int i = size / 2; i >= 1; i--)
      {
         HeapElement 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
            if (c < size &&
                heap[c].key.compareTo(heap[c + 1].key) < 0)
               c++;
   
            // can we put y in heap[c/2]?
            if (y.key.compareTo(heap[c].key) >= 0)
               break;  // yes
   
            // no
            heap[c / 2] = heap[c]; // move child up
            c *= 2;                // move down a level
         }
         heap[c / 2] = y;
      }
   }
   
   public String toString()
   {
      StringBuffer s = new StringBuffer(); 
      s.append("The " + size + " elements are [");
      for (int i = 1; i <= size; i++)
      {
         if (i != 1)  // not first element
            s.append(", ");
         s.append(heap[i]);
      }
      s.append("]");

      return new String(s);
   }
}

---

(d) A test program and output appear in the files MaxHeapWithKey.*.