public class MaxHeap {

	private int [] heap; // heap has meaningful elements at locations 1...size
	private int size;
	
	MaxHeap (int maxElements) {
		heap = new int [maxElements+1];
	}
	
	public void insert (int value) {
		// resize the array if necessary
		if (size == heap.length-1) {
			int [] newHeap = new int [heap.length*2];
			for (int i = 1; i<heap.length; i++)
				newHeap[i]=heap[i];
			heap = newHeap;
		}
		
		heap[++size] = value;
		swim(size);
	}
	
	private void swap (int i, int j) {
		int temp = heap[i];
		heap[i] = heap[j];
		heap[j]=temp;
	}
	
	private void swim (int pos) {
		while (pos>1 && heap[pos]>heap[pos/2]) {
			swap(pos, pos/2);
			pos/=2;
		}		
	}
	
	public int removeMax () {
		int max = heap[1];
		heap[1]=heap[size--];
		sink(1);
		return max;
	}
	
	private void sink (int pos) {
		while (true) {
			int child = 2*pos;
			if (child>size)
				break;
			if (child<size && heap[child]<heap[child+1])
				child++;
			if (heap[pos]<heap[child]) {
				swap(pos, child);
				pos = child;
			}
			else
				break;
		}
	}
	
	
}