public class Heap extends Tree {

    public boolean isEmpty () {
	return size() == 0;
    }

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

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

    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));
	}
    }

    // 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);
    }
}