public class MaxHeap implements SeqStructure {

    private BinaryNode root;
    private BinaryNode finger;   //a cursor into the data structure
    private BinaryNode previous; //previous is one step behind finger
    private int size;
    private int nComparisons;
    
    public MaxHeap() {
	root= null;
	size = 0;
	nComparisons = 0;
    }
    
    public String toString() {
	return root.toString();
    }
    
    public String toTree() {
	return root.toTree();
    }

    public int numComparisons() {
	return nComparisons;
    }

    public boolean isEmpty() {
	return size == 0;
    }
    
    public int size() {
	return this.size;
    }
    
    public Object get() {
	
	// check for empty heap
	if (isEmpty()) {
	    System.out.println("Empty heap!");
	    return null;
	}
	
	// extract the maximum element
	Comparable max = (Comparable)(root.getItem());
	
	// if empty tree remains after deletion, update is easy
	if (size == 1) {
	    root = null;
	    size = 0;
	    return max;
	}

	// non-empty tree will remain after deletion of root
	// move down the tree to PARENT of node whose number is size
	// easy to show that number of this parent node is size/2
	heapDecoder d = new heapDecoder(size/2, 2);
	finger = root;
	while (d.hasMoreDigits()) 
	    if (d.getNextDigit() == 0) 
		finger = finger.getLeft();
	    else 
		finger = finger.getRight();
	
	// set root value to value in node whose number is size
	// delete node whose number is size
	if (size%2 == 0) { // left child
	    root.setItem(finger.getLeft().getItem());
	    finger.setLeft(null);
	}
	else {
	    root.setItem(finger.getRight().getItem());
	    finger.setRight(null);
	}
	
	// now walk down the tree from the root restoring the heap property
	BinaryNode dNode = root; // the disturbed node
	BinaryNode cNode;        // max child of dNode
	while (true) {
	    // check the left and right children for heap property
	    BinaryNode l = dNode.getLeft();
	    BinaryNode r = dNode.getRight();
	    
	    // find the max kid
	    if (l == null) break; //d must be a leaf node
	    if (r == null) cNode = l;
	    else { // dNode has two children
		if (((Comparable)l.getItem()).compareTo(r.getItem()) < 0) 
		    cNode = r;
		else cNode = l;
		nComparisons++;
	    }
	    
	    // swap maxkid with parent maybe?
	    nComparisons++;
	    if (((Comparable)dNode.getItem()).compareTo(cNode.getItem()) < 0) {
		// swap parent and child data fields and update dNode
		Object o = dNode.getItem();
		dNode.setItem(cNode.getItem());
		cNode.setItem(o);
		dNode = cNode;
	    }
	    else // no need to go further down heap
		break;
	}
	size = size - 1;
	return max;
    }
    
    
    public void put(Object o) {
	
	Comparable p = (Comparable)o;
	size = size + 1;
	if (root == null) {
	    root = new BinaryNode(p);
	    return;
	}
	
	// otherwise move down the tree to parent of node whose number is size
	// along the way, compare values to maintain heap property
	heapDecoder d = new heapDecoder(size/2,2);
	finger = root;
	while (true) {
	    if (p.compareTo(finger.getItem()) > 0) {
		//swap
		Comparable temp = (Comparable) finger.getItem();
		finger.setItem(p);
		p = temp;
	    }
	    nComparisons++;
	    
	    if (! d.hasMoreDigits()) {
		BinaryNode n = new BinaryNode(p);
		if (size%2 == 0) //set left
		    finger.setLeft(n);
		else
		    finger.setRight(n);
		break;
	    }
	    else {
		if (d.getNextDigit() == 0) //go left
		    finger = finger.getLeft();
		else //go right
		    finger = finger.getRight();
	    }
	}
    }
    
    // inner class that implements an iterator for translating heap position numbers
    // into paths down the tree from root to that position
    // base will usually be 2 (binary heaps) but it can be set arbitrarily
    // for more general n-ary heaps
    private class heapDecoder {
	private int position;
	private int base;
	
	public heapDecoder(int pos, int base){
	    position = pos;
	    this.base = base;
	}
	
	public int getNextDigit() {
	    int rem = position % base;
	    position = position/base;
	    return rem;
	}
	
	public boolean hasMoreDigits() {
	    return (position > 1);
	}
    }
}