public class Heap extends Tree {

    // heapGet: return the ith element of the vector or null if
    // i is out of bounds
    private Comparable heapGet (int i) {
	if (i < 1 || i > size()) return null;
	return (Comparable) get (i);
    }

    // compare: anything is better than nothing
    private int compare (Comparable a, Comparable b) {
	if (a == null && b == null) return 0;
	if (a == null) return -1;
	if (b == null) return 1;
	return a.compareTo (b);
    }

    public void insert (Comparable comp) {
	// insert
	add (comp);
	int i = size();

	// reheapify
	while (i > 1) {
	    Comparable node = heapGet (i); 
	    Comparable par = heapGet (parent (i));
	    if (node.compareTo (par) <= 0) break;
	    swap (i, parent(i));
	    i = parent (i);
	}
    }

    public Comparable remove () {

	// swap first and last, then remove last
	int first = 1;
	int last = size();
	swap (first, last);
	Comparable result = (Comparable) remove (last);

	// restore the heap property before returning
	reheapify (1);
	return result;
    }

    // reheapify: restore the heap property after something
    // is removed
    public void reheapify (int i) {
	if (i >= size()) return;

	Comparable node = heapGet (i); 
	Comparable left = heapGet (left (i));
	Comparable right = heapGet (right (i));

        if (compare (node, left) >= 1 && compare (node, right) >= 1) return;
	if (compare (left, right) >= 1) {
	    swap (i, left (i));
	    reheapify (left (i));
	} else {
	    swap (i, right (i));
	    reheapify (right (i));
	}
    }
}