PriorityQueue

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N = 0;

    public MaxPQ (int max) {
        pq = (Key[]) new Comparable[max+1]; //max+1 leaves one slot wasted memory, but saves a few calculations with every "step" taken through the three.
    }

    public boolean isEmpty () {
        return this.N==0;
    }

    public int size (){
        return this.N;
    }

    public void insert (Key k) {
        pq[++N] = k;
        swim(N);
    }

    public Key eatMax() {
        Key max = pq[1];
        swap(1, N);
        pq[N--] = null;
        drown(1);
        return max;
    }

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

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

    private void swim (int k) {
        while (k>1 && less(k/2, k)) { //as long as my parents<me, swap me with my parents
            swap(k/2, k);
        }
    }

    private void drown (int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j<N && less(j, j+1)) j++;   //pick my bigest child!
            if (!less(k, j)) break;     //if my biggest child<=me, we're done
            swap(k, j);             //else swap me and my child
            k=j;                //I get a second childhood!
        }
    }

    public Key[] getList() {
        return pq;
    }
}