import java.util.*;

/* Define a Max-Heap
 * @author Lin Chen
 * @since 10.02.2017
 */
public class P
{
	private int array [];
	private int size;
	private int length;

	/* Initialize array with the array in CLRS
	 */
	public P()
	{
		array = getArray();
		size = array.length;
		length = size;
		buildMaxHeap(array);

		System.out.println(this);
	}

	/* Get the front element
	 * @return front
	 */
	// O(1)
	public int peek()
	{
		if(size < 1)
			return -1;

		return array[0];
	}

	/* Dequeue
	 * @return front
	 */
	// O(lgn)
	public int poll()
	{
		if(size < 1)
			return -1;
		int max = array[0];
		array[0] = array[size-1];
		size--;
		maxHeapify(array, 0, size-1);

		return max;
	}

	/* Increase the specific element
	 * @param i index of the element
	 * @param key value that change to
	 */
	// O(lgn)
	public void increase(int i, int key)
	{
		if(key < array[i])
			return;
		array[i] = key;
		while(i > 0 && array[getParent(i)] < array[i])
		{
			int temp = array[getParent(i)];
			array[getParent(i)] = array[i];
			array[i] = temp;
			i = getParent(i);
		}
	}

	/* Insert an element
	 * @param key insert value
	 */
	// O(lgn)
	public void insert(int key)
	{
		if(size >= length)
		{
			int [] array2 = new int[size*2];
			for(int i = 0; i < size; i++)
				array2[i] = array[i];
			array = array2;
			length *= length;
		}
		array[size] = key;
		size++;
		increase(size-1, key);
	}

	/* Check whether or not has next element
	 * @return true if has more element; false otherwise
	 */
	public boolean hasNext()
	{
		return (size > 0);
	}

	/* Get the size of queue
	 * @return queue size
	 */
	public int size()
	{
		return size;
	}

	/* Get the example in CLRS
	 * @return an intger array
	 */
	public static int [] getArray()
	{
		int array [] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};

		return array;
	}

	/* Get the left child
	 * @param i index of current node
	 * @return index of left child
	 */
	public static int getLeft(int i)
	{
		return i*2+1;
	}

	/* Get the right child
	 * @param i index of current node
	 * @return index of right child
	 */
	public static int getRight(int i)
	{
		return i*2+2;
	}

	public static int getParent(int i)
	{
		return (i-1)/2;
	}

	/* Maintin the max-heap property of a subtree rooted at index i
	 * @param array an integer array
	 * @param i index of current node
	 * @param n index of last node of the subtree
	 */
	// O(lgn)
	public static void maxHeapify(int [] array, int i, int n)
	{
		int l = getLeft(i);//get left child
		int r = getRight(i);//get right child

		int largest = i;

		if(l <= n && array[l] > array[i])
			largest = l;

		if(r <= n && array[r] > array[largest])
			largest = r;

		if(largest != i)
		{
			int temp = array[i];
			array[i] = array[largest];
			array[largest] = temp;
			maxHeapify(array, largest, n);
		}
	}

	/* Create the heap tree for input array
	 * @param array an integer array
	 */
	// O(nlgn)
	public static void buildMaxHeap(int [] array)
	{
		for(int i = (array.length/2-1); i >= 0; i--)
		{
			maxHeapify(array, i, array.length-1);
		}
	}

	/* Override toString function
	 */
	@Override
	public String toString()
	{
		String str = "";
		for(int i = 0; i < size; i++)
			str = str + " " + array[i];

		return str;
	}
}