/*************************************************************************
 *  Compilation:  javac PQint.java
 *  Execution:    java PQ
 *  
 *  Priority queue (of integers) implementation with binary heap.
 *
 * Acknowledgement: 
 * A modified version of code originally 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 int[] pq;          // store elements at index 1 to N
    private int N;             // number of elements

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

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

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

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

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

    int delMax() {
	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] < pq[j]);
    }

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


    /***********************************************************************
     * Test routine.
     **********************************************************************/
    public static void main(String[] args) {
	PQ pq = new PQ();
	pq.insert(2);
	pq.insert(3);
	pq.insert(7);
	pq.insert(5);
	while (!pq.isEmpty())
	    System.out.println(pq.delMax());
    }

}