package alg;

import java.util.Arrays;
import java.util.Collection;

public class BinaryHeap<T extends Comparable<? super T>> {
	private Object[] m_itemArray;
	private int m_length;
	private int m_capacity;

	public BinaryHeap(Collection<? extends T> items) {
		m_itemArray = items.toArray();
		m_length = m_itemArray.length;
		m_capacity = m_itemArray.length;
		heapify();
	}

	private void heapify() {
		// Heapify from the bottom up by sifting down the nodes at each level.
		int i = (m_length - 1) / 2;
		for (; i >= 0; --i) {
			siftDown(i, getAt(i));
		}
	}

	public boolean empty() {
		return m_length == 0;
	}

	public int size() {
		return m_length;
	}

	public boolean add(T element) {
		ensureCapacity(m_length + 1);

		// To insert into a heap, push it to the end of the array
		// and sift up.
		siftUp(m_length++, element);

		return true;
	}

	public T peek() {
		return getAt(0);
	}

	public T pop() {
		T item = peek();
		siftDown(0, getAt(--m_length));
		return item;
	}

	private void siftUp(int i, T ele) {
		// Compare node i to its parent. If it's less than parent, then swap and
		// recurse up.
		int parent = (i - 1) / 2;
		if (0 < i && ele.compareTo(getAt(parent)) < 0) {
			m_itemArray[i] = m_itemArray[parent];
			siftUp(parent, ele);
		} else {
			m_itemArray[i] = ele;
		}
	}

	private T getAt(int i) {
		@SuppressWarnings("unchecked")
		T t = (T) m_itemArray[i];
		return t;
	}

	@SuppressWarnings("unchecked")
	private void siftDown(int i, T ele) {
		// Compare node i to its children. If the minimum is less than the node,
		// then swap and recurse down.
		int j = i;
		T cmp = ele;

		int child = 2 * i + 1;
		if (child < m_length && getAt(child).compareTo(cmp) < 0) {
			j = child;
			cmp = (T) m_itemArray[child];
		}
		child++;
		if (child < m_length && getAt(child).compareTo(cmp) < 0) {
			j = child;
			cmp = (T) m_itemArray[child];
		}

		m_itemArray[i] = cmp;
		if (j != i) {
			siftDown(j, ele);
		}
	}

	private void ensureCapacity(int cap) {
		if (cap > m_capacity) {
			int nextCap = Math.max((m_capacity / 2) * 3, cap);
			Object[] nextItems = new Object[nextCap];
			System.arraycopy(m_itemArray, 0, nextItems, 0, m_length);

			m_itemArray = nextItems;
			m_capacity = nextCap;
		}
	}

	public static void main(String[] args) {
		BinaryHeap<Integer> heap = new BinaryHeap<>(Arrays.asList((Integer) 9, 2, 7, 6, 4, 1, 8, 5, 3));

		heap.add(12);
		heap.add(-1);
		heap.add(10);

		while (!heap.empty()) {
			System.out.println(heap.pop());
		}
	}
}