/*************************************************************************
 *  Compilation:  javac PQ.java
 *  Execution:    java PQ
 *  
 *  Priority queue implementation with binary heap.
 *
 * Acknowledgement: 
 * This source code is part of a forthcoming book by
 * Robert Sedgewick and Kevin Wayne, responsibles for the COS 126
 * course at Princeton University
 * url: http://www.cs.princeton.edu/introcs/home/
 *
 *************************************************************************/

class PQ {
   private Comparable[] pq;          // store elements at index 1 to N
   private int N;                    // number of elements

   // set inititial size of heap to hold size elements
   public PQ(int size) {
      pq = new Comparable[size + 1];
      N = 0;
   }

   // set inititial size of heap to hold 0 elements
   public PQ() { this(0); }


   boolean isEmpty() { return N == 0; }
   int size()        { return N;      }

   void insert(Comparable item) {
      // double size of array if necessary
      if (N >= pq.length - 1) {
         Comparable[] pq = new Comparable[2*(N+1)];
         System.arraycopy(this.pq, 0, pq, 0, N + 1);
         this.pq = pq;
      }

      pq[++N] = item;
      swim(N);
   }

   Comparable delMax() {
      if (N == 0) return null;
      exch(1, N);
      sink(1, N-1);
      return pq[N--];
   }

   private void swim(int k) {
      while (k > 1 && less(k/2, k)) {
         exch(k, k/2);
         k = k/2;
      }
   }

   private void sink(int k, int N) {
      while (2*k <= N) {
         int j = 2*k;
         if (j < N && less(j, j+1)) j++;
         if (!less(k, j)) break;
         exch(k, j);
         k = j;
      }
   }

  /***********************************************************************
   * Helper functions.
   **********************************************************************/
   private boolean less(int i, int j) {
      return pq[i].compareTo(pq[j]) < 0;
   }

   private void exch(int i, int j) {
      Comparable swap = pq[i];
      pq[i] = pq[j];
      pq[j] = swap;
   }


  /***********************************************************************
   * Test routine.
   **********************************************************************/
   public static void main(String[] args) {
      PQ pq = new PQ();
      pq.insert("this");
      pq.insert("is");
      pq.insert("a");
      pq.insert("test");
      while (!pq.isEmpty())
         System.out.println(pq.delMax());
   }

}