public class MyIntMaxHeap implements MyIntHeap {
	public static final int CAPACITY = 2;
	private int size;
	private int[] data;

	public MyIntMaxHeap() {
		size = 0;
		data = new int[CAPACITY];
	}

	public void insert(int key) {
		if (size == data.length - 1) {
			data = doubleSize(data);
		}
		size++;
		int currentIndex = size;
		data[currentIndex] = key;
		while (currentIndex != 1 && data[currentIndex] > data[currentIndex / 2]) {
			swap(currentIndex, currentIndex / 2);
			currentIndex /= 2;
		}
	}

	public int remove() {
		if (size == 0) {
			throw new RuntimeException("No element in the heap");
		}
		int max = data[1];
		if (size != 1) {
			int currentIndex = 1;
			data[currentIndex] = data[size];
			while (currentIndex * 2 < size) {
				int childToSwap = data[currentIndex * 2];
				int nextIndex = currentIndex * 2;
				if (currentIndex * 2 + 1 < size && data[currentIndex * 2 + 1] > data[currentIndex * 2]) {
					childToSwap = data[currentIndex * 2 + 1];
					nextIndex = currentIndex * 2 + 1;
				}
				if (data[currentIndex] >= childToSwap) {
					break;
				}
				swap(currentIndex, nextIndex);
				currentIndex = nextIndex;
			}
		}
		size--;
		return max;
	}

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

	private int[] doubleSize(int[] array) {
		int[] doubleSizeArray = new int[array.length * 2];
		for (int i = 0; i < array.length; i++) {
			doubleSizeArray[i] = array[i];
		}
		return doubleSizeArray;
	}

	private void swap(int firstIndex, int secondIndex) {
		int tmp = data[firstIndex];
		data[firstIndex] = data[secondIndex];
		data[secondIndex] = tmp;
	}
}