// Jacob Whitehill
import java.util.NoSuchElementException;

class HeapImpl12<T extends Comparable<? super T>> implements Heap12<T> {
	private static final int INITIAL_CAPACITY = 128;
	private int _numElements;
	private T[] _storage;
	private int _k;
	
	public HeapImpl12 (T[] storage, int k) {
		if (k <= 1) {
			throw new IllegalArgumentException();
		}

		_k = k;
		_storage = storage;
		_numElements = 0;
	}

	public HeapImpl12 () {
		this(2);
	}

	@SuppressWarnings("unchecked")
	public HeapImpl12 (int k) {
		if (k <= 1) {
			throw new IllegalArgumentException();
		}

		_k = k;
		clear();
	}

	public int size () {
		return _numElements;
	}

	public int height (T data) {
		int index = indexOf(data);
		if (index < 0) {
			throw new NoSuchElementException();
		}

		int height = 0;
		while ((index = parent(index)) >= 0) {
			height++;
		}
		return height;
	}

	public boolean contains (T data) {
		return indexOf(data) != -1;
	}

	@SuppressWarnings("unchecked")
	public void add (T data) {
		if (_numElements == _storage.length) {
			final T[] newStorage = (T[]) new Comparable[_storage.length * 2];
			System.arraycopy(_storage, 0, newStorage, 0, _storage.length);
			_storage = newStorage;
		}

		_storage[_numElements] = data;
		_numElements++;

		bubbleUp(_numElements - 1);
	}

	private int indexOf (T data) {
		for (int i = 0; i < _numElements; i++) {
			if (_storage[i].equals(data)) {
				return i;
			}
		}

		return -1;
	}

	// This method is non-obvious!
	public void remove (T data) {
		final int index = indexOf(data);
		if (index < 0) {
			throw new NoSuchElementException();
		}

		_storage[index] = _storage[_numElements - 1];
		_numElements--;

		if (_storage[index].compareTo(data) < 0) {  // New element smaller than the one we removed
			trickleDown(index);
		} else if (_storage[index].compareTo(data) > 0) {  // New element bigger than the one we removed
			bubbleUp(index);
		}
	}

	public T peekLargest () {
		if (_numElements == 0) {
			throw new NoSuchElementException();
		}

		return _storage[0];
	}

	public T removeLargest () {
		if (_numElements == 0) {
			throw new NoSuchElementException();
		}

		final T data = _storage[0];
		_storage[0] = _storage[_numElements - 1];
		_numElements--;
		trickleDown(0);

		return data;
	}

	private int parent (int index) {
		return index == 0 ? -1 : ((index - 1) / _k);
	}

	// Returns index of ith child of node at index.
	private int child (int index, int i) {
		return _k * index + i + 1;
	}

	private void bubbleUp (int index) {
		while (index > 0 && _storage[index].compareTo(_storage[parent(index)]) > 0) {
			swap(index, parent(index));

			index = parent(index);
		}
	}

	private void swap (int index1, int index2) {
		final T temp = _storage[index1];
		_storage[index1] = _storage[index2];
		_storage[index2] = temp;
	}

	private void trickleDown (int index) {
		while (child(index, 0) < _numElements) {  // As long as there's at least one child
			// Determine which child is largest
			int childIndex = child(index, 0);
			for (int i = 1; i < _k && child(index, i) < _numElements; i++) {
				if (_storage[child(index, i)].compareTo(_storage[childIndex]) > 0) {
					childIndex = child(index, i);
				}
			}

			// If larger child is bigger than we are, then swap
			if (_storage[index].compareTo(_storage[childIndex]) < 0) {
				swap(index, childIndex);
				index = childIndex;
			} else {  // Else, we're done trickling down
				break;
			}
		}
	}

	@SuppressWarnings("unchecked")
	public void clear () {
		_storage = (T[]) new Comparable[INITIAL_CAPACITY];
		_numElements = 0;
	}
}