import java.util.NoSuchElementException;
import java.util.Random;

/** An array-based maxheap.

    Adapted from Carrano Chapter 26.
*/
public class MaxHeap<E extends Comparable<E>>
{
   private E[] heap;
   private int lastIndex;

   public MaxHeap(int k)
   {
      // The cast is safe because the new array contains all null entries
      @SuppressWarnings("unchecked")
      E[] tmp = (E[])new Comparable[10];
      heap = tmp;
      lastIndex = 0;
   }

   // 26.8
   public void add(E newEntry)
   {
      int newIndex = lastIndex + 1;
      int parentIndex = newIndex / 2;
      while ((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0)
      {
         heap[newIndex] = heap[parentIndex];
         newIndex = parentIndex;
         parentIndex = newIndex / 2;
      }
      heap[newIndex] = newEntry;
      lastIndex++;
      ensureCapacity();
   }

   private void ensureCapacity()
   {
      if (lastIndex >= heap.length - 1)
      {
         // The cast is safe because the new array contains all null entries
         @SuppressWarnings("unchecked")
         E[] tmp = (E[])new Comparable[heap.length * 2];
         for (int i = 0; i <= lastIndex; i++)
         {
            tmp[i] = heap[i];
         }
         heap = tmp;
      }
   }

   // 26.12
   public E removeMax()
   {
      if (lastIndex == 0)
         throw new NoSuchElementException();
      E root = heap[1];          // Return value
      heap[1] = heap[lastIndex]; // Form a semiheap
      lastIndex--;               // Decrease size
      reheap(1);                 // Transform to a heap
      return root;
   }

   // 26.11
   private void reheap(int rootIndex)
   {
      boolean done = false;
      E orphan = heap[rootIndex];
      int leftChildIndex = 2 * rootIndex;
      while (!done && (leftChildIndex <= lastIndex))
      {
         int largerChildIndex = leftChildIndex; // Assume larger
         int rightChildIndex = leftChildIndex + 1;
         if ((rightChildIndex <= lastIndex) &&
               heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0)
         {
            largerChildIndex = rightChildIndex;
         }
         if (orphan.compareTo(heap[largerChildIndex]) < 0)
         {
            heap[rootIndex] = heap[largerChildIndex];
            rootIndex = largerChildIndex;
            leftChildIndex = 2 * rootIndex;
         }
         else
         {
            done = true;
         }
         heap[rootIndex] = orphan;
      }
   }

   // This method is here for debugging and grading purposes.
   public void display()
   {
      for (int i = 1; i <= lastIndex; i++)
         System.out.print(heap[i] + " ");
      System.out.println();
   }

   // Please do not change any code in main.
   public static void main(String[] args)
   {
      for (int k = 2; k < 6; k++)
      {
         System.out.println("------------------------");
         System.out.println("k = " + k);
         Random rand = new Random(55057);
         MaxHeap<Integer> heap = new MaxHeap<Integer>(k);
         for (int i = 0; i < 20; i++)
            heap.add(rand.nextInt(100));
         heap.display();
         for (int i = 0; i < 20; i++)
            System.out.print(heap.removeMax() + " ");
         System.out.println();
      }
   }
}