import java.util.Vector;

public class Heap {

    Vector<Integer> els = new Vector<Integer>();

    private int sink(int n, int v) { 
	// n is the position, v is the value. Returns
	// the right position.
	int left =  2 * n + 1;
	int right = 2 * n + 2; 
	int big;
	if(left < els.size()) {
	    if(right < els.size()) 
		big = (els.get(left) < els.get(right) ?
		       right : left);
	    else
		big = left;
	    if(v < els.get(big)) {
		els.set(n, els.get(big));
		return sink(big, v);
	    }
	    else
		return n;
	}
	else 
	    return n;
    }
		
    private int swim(int n, int v) {
	if(n > 0) {
	    int par = (n - 1) / 2;
	    if(v > els.get(par)) {
		els.set(n, els.get(par));
		return swim(par, v);
	    }
	    else
		return n;
	}
	else
	    return n;
    }

    public void add(int v) {
	els.add(v);
	int n = swim(els.size() - 1, v);
	els.set(n, v);
    }

    public int remove() {
	int t = els.get(0);
	int v = els.lastElement();
	els.remove(els.size()-1);
	int n = sink(0, v);
	els.set(n, v);
	return t;
    }

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

    public static void main(String args[]) {
	Heap heap = new Heap();
	heap.add(9);
	heap.add(8);
	heap.add(7);
	System.out.println(heap);
	System.out.println(heap.remove());
	System.out.println(heap);
	heap.add(12);
	System.out.println(heap);
	System.out.println(heap.remove());
	System.out.println(heap);
    }
}