public class BinaryHeap {
	public BinaryHeap( int capacity ){
		currentSize = 0;
		array = new Comparable [ capacity + 1];
	}
	public void insert( Comparable x){
		// percolate up
		currentSize++;
		int hole = currentSize;
		int parent = hole/2;
		while( hole > 1 && x.compareTo( array[parent]) < 0){
			array[hole] = array[parent];
			hole = parent;
			parent = hole/2;
		}
		array[hole] = x;
	}
	public void printHeap(){
		int i;
		for(i=1; i<=currentSize; i++)
			System.out.print(array[i] + " ");
		System.out.println();
	}
	public Comparable deleteMin(){
		Comparable minItem = array[1];
		array[1] = array[ currentSize];
		currentSize--;
		percolateDown(1);
		return minItem;
	}
	private void percolateDown(int hole){
		int child;
		Comparable tmp = array[hole];
		while( hole * 2 <= currentSize){
			child = hole * 2;
			if( child != currentSize &&
					array[child+1].compareTo( array[child]) < 0){
				child++;
				hole = child;
			}
			if( array[child].compareTo(tmp) < 0){
				array[hole] = array[child];
				hole = child;
			}else
				break;
		}
		array[hole] = tmp;
	}
	private Comparable[] array;
	private int currentSize;
}