import java.util.ArrayList;
import java.util.Collection;
import java.util.NoSuchElementException;
import java.util.Comparator;

public class BinaryHeap<T> implements PriorityQueue<T> {
    private ArrayList<T> nodes;
    private Comparator<? super T> priority;
    
    /**
     * Constructor with no parameters
     */
    public BinaryHeap() {
        nodes = new ArrayList<T>();
        nodes.add(null);
        priority = null;
    }
    
    /**
     * Constructor with a Comparator parameter
     */
    public BinaryHeap(Comparator<? super T> priority) {
        nodes = new ArrayList<T>();
        nodes.add(null);
        this.priority = priority;
    }
    
    /**
     * Constructor from an array
     */
    public BinaryHeap(Collection<? extends T> a) {
        constructHeap(a);
    } // end constructor
    
    /**
     * Constructor from an array a Comparator
     */
    public BinaryHeap(Collection<? extends T> a, Comparator<T> priority) {
        this.priority = priority;
        constructHeap(a);
    } // end constructor
    
    private void constructHeap(Collection<? extends T> a) {
        nodes = new ArrayList<T>();
        nodes.add(null);
        for( T x : a ) {
            nodes.add(x);
        } // end for
        for( int i = size()/2; i > 0; i-- ) {
            pushDown(i);
        } // end for
    } // end constructHeap
    
    /**
     * Get the number of elements in the PriorityQueue
     * @return the number of elements in the PriorityQueue
     */
    public int size() {
        return nodes.size()-1;
    }
    
    // These are the methods of the PriorityQueue interface
    
    /**
     * Clear the heap
     */
    public void removeAll() {
        nodes = new ArrayList<T>();
        nodes.add(null);
    }
    
    /**
     * Check for an empty heap
     * @return true if the heap is empty; false otherwise
     */
    public boolean isEmpty() {
        return size() == 0;
    }
    
    /**
     * Insert an element into the Heap and heapify
     * @param x is the element inserted
     */
    public void add(T x) {
        nodes.set(0,x);
        nodes.add(x);
        pushUp(size());
    }
    
    /**
     * Delete the minimum element from the Heap
     * @return the delete element
     */
    public T removeMin() {
        if( size() == 0 ) throw new NoSuchElementException("Empty Heap Error");
        T save = nodes.get(1);
        if ( size() == 1 ) {
            nodes.remove(size());
        } else {
            nodes.set(1,nodes.remove(size()));
        }// end if
        pushDown(1);
        return save;
    }
    
    /**
     * Get the minimum element in the Heap
     * @return the minimum element
     */
    public T getMin() {
        if( size() == 0 ) throw new NoSuchElementException("Empty Heap Error");
        return nodes.get(1);
    }// end getMin
    
    /**
     * the toString() method
     * @return a String representation of the heap
     */
    public String toString() {
        String out = "";
        for( T x : nodes.subList(1,nodes.size()) ) {
            out += x + " ";
        }// end for
        return out;
    }// end toString
    
    /**
     * Get the prioity object used in the PriorityQueue
     * @return the priority as a comparator object
     */
    public Comparator<? super T> priority() {
        return priority;
    } // end Comparator
    
    
    // These are the private methods
    
    private int parent(int n) {
        return n/2;
    }// end parent
    
    private boolean isLeaf(int n) {
        return 2*n > size();
    }// end isLeaf
    
    private void pushUp(int n) {
        if( compare(nodes.get(parent(n)),nodes.get(n)) > 0 ) {
            T hold = nodes.get(n);
            nodes.set(n,nodes.get(parent(n)));
            nodes.set(parent(n),hold);
            pushUp(parent(n));
        } // end if
    }// end pushUp
    
    private int leftChild(int n) {
        return 2*n;
    }// end leftChild
    
    private int rightChild(int n) {
        return 2*n+1;
    }// end rightChild
    
    private int minChild(int n) {
        int min = leftChild(n);
        if( min == size() ) return min; // no right child
        if( compare(nodes.get(min),nodes.get(rightChild(n))) > 0 ) {
            min = rightChild(n);
        }// end if
        return min;
    }// end minChild
    
    private void pushDown(int n) {
        if( isLeaf(n) ) return; // heap is OK
        int minChild = minChild(n);
        if( compare(nodes.get(n),nodes.get(minChild)) > 0 ) {
            T hold = nodes.get(n);
            nodes.set(n,nodes.get(minChild));
            nodes.set(minChild,hold);
            pushDown(minChild);
        } // end if
    }// end pushDown
    
    private int compare(T left, T right) {
        if( priority == null ) {
            return ((Comparable)left).compareTo(right);
        } else {
            return priority.compare(left,right);
        } // end if
    } // end compare
    
} // end BinaryHeap