public class Heap {
	// Constant
	private static final int DEF_MAX_HEAP_SIZE = 10; // Default maximum heap
														// size
	private static final int FRONT = 1;
	// Data members
	private int size; // Actual number of elements in the heap
	private int[] element; // Array containing the heap elements

	public Heap() // Constructor: default size
	{
		setup(DEF_MAX_HEAP_SIZE);
	}

	public Heap(int maxNumber) // Constructor: specific size
	{
		setup(maxNumber);
	}

	// Class methods
	private void setup(int maxNumber) // Called by constructors only
	{
		size = 0;
		element = new int[maxNumber + 1];
		element[0] = Integer.MAX_VALUE;
	}

	private int parent(int pos) {
		return pos / 2;
	}

	private int leftChild(int pos) {
		return (2 * pos);
	}

	private int rightChild(int pos) {
		return (2 * pos) + 1;
	}

	private boolean isLeaf(int pos) {
		if (pos >= (size / 2) && pos <= size) {
			return true;
		}
		return false;
	}

	private void swap(int fpos, int spos) {
		int tmp;
		tmp = element[fpos];
		element[fpos] = element[spos];
		element[spos] = tmp;
	}

	private void maxHeapify(int pos) {
		if (!isLeaf(pos)) {
			if (element[pos] < element[leftChild(pos)] || element[pos] < element[rightChild(pos)]) {
				if (element[leftChild(pos)] > element[rightChild(pos)]) {
					swap(pos, leftChild(pos));
					maxHeapify(leftChild(pos));
				} else {
					swap(pos, rightChild(pos));
					maxHeapify(rightChild(pos));
				}
			}
		}
	}

	public void maxHeap() {
		for (int pos = (size / 2); pos >= 1; pos--) {
			maxHeapify(pos);
		}
	}

	// Heap manipulation methods
	public void insert(int newElement) // Insert element
	{
		element[++size] = newElement;
		int current = size;
		while (element[current] > element[parent(current)]) {
			swap(current, parent(current));
			current = parent(current);
		}
	}

	public int removeMax() // Remove max pty element
	{
		int popped = element[FRONT];
		element[FRONT] = element[size--];
		maxHeapify(FRONT);
		return popped;
	}

	public void clear() // Clear heap
	{
		size = 0;
	}

	static int log(int x, int base) {
		return (int) (Math.log(x) / Math.log(base));
	}

	public int getLevel() // return number of level
	{
		int level = (int) log(size, 2);
		if (size == (int) Math.pow(2, level))
			return level;
		else
			return level + 1;
	}

	// Heap status methods
	public boolean isEmpty() // Heap is empty
	{
		return size == 0;
	}

	public boolean isFull() // Heap is full
	{
		return size == element.length;
	}

	// Output the heap structure - used in testing/debugging
	public void showStructure() {
		for (int i = 1; i <= size / 2; i++) {
			System.out.print(" PARENT : " + element[i] + " LEFT CHILD : " + element[2 * i] + " RIGHT CHILD :"
					+ element[2 * i + 1]);
			System.out.println();
		}
	}

	// Recursive partner of the showStructure() method
	private void showSubtree(int index, int level) {
	}
}