import java.util.Vector;

public class Heap {
    Vector v;

    public Heap () {
	v = new Vector ();
	v.add ("narf");
    }

    public boolean empty () {
	return v.size() == 1;
    }

    public void insert (Comparable c) {
	v.add (c);

	int i = v.size()-1;
	while (i>1) {
	    int parent = i/2;
	    if (compare (i, parent) > 0) {
		swap (i, parent);
	    } else {
		break;
	    }
	    i = parent;
	}
    }

    private int compare (int i, int j) {
	Comparable c1 = (Comparable) get (i);
	Comparable c2 = (Comparable) get (j);
	//System.out.println (c1 + " compared to " + c2);
	if (c1 == null) {
	    if (c2 == null) {
		return 0;
	    } else {
		return -1;
	    }
	}
	if (c2 == null) return 1;
	return c1.compareTo (c2);
    }

    private Object get (int i) {
	if (i >= v.size()) {
	    return null;
	} else {
	    return v.get(i);
	}
    }

    private void swap (int i, int j) {
	Object temp = v.get (i);
	v.set (i, v.get (j));
	v.set (j, temp);
    }

    public Object remove () {
	int i = v.size()-1;
	swap (1, i);
	Object result = v.remove (i);
	reheapify (1);
	return result;
    }

    private void reheapify (int i) {
	int left = 2*i;
	int right = 2*i + 1;
	boolean winleft = compare (i, left) >= 0;
	boolean winright = compare (i, right) >= 0;

	if (winleft && winright) return;
	if (compare (left, right) > 0) {
	    swap (i, left);
	    reheapify (left);
	} else {
	    swap (i, right);
	    reheapify (right);
	}
    }

    private void print () {
	for (int i=0; i<v.size(); i++) {
	    System.out.print (v.get(i) + " ");
	}
	System.out.println ();
    }

    public static void main (String[] args) {
	Heap h = new Heap ();
	for (int i=0; i<10; i++) {
	    h.insert (new Integer (randInt(1, 100)));
	}
	while (!h.empty()) {
	    //h.print ();
	    System.out.println (h.remove());
	}
    }

    public static int randInt (int low, int high) {
	while (true) {
	    int x = (int)(Math.random() * (high-low+1) + low);
	    if (x >= low && x <= high) return x;
	} 
    }

}