// read from keyboard
import java.util.*;

class MinIntHeapSort{
	private int capacity = 10;
	int size = 0;

	int items[] = new int[capacity];

	// help methods

	private int getLeftChildIndex(int parentIndex){
		return 2*parentIndex + 1;
	}
	private int getRightChildIndex(int parentIndex){
		return 2*parentIndex + 2;
	}
	private int getParentIndex(int childIndex){
		return (childIndex - 1)/2;
	}

	private boolean hasLeftChild(int index){
		return getLeftChildIndex(index) < size;
	}
	private boolean hasRightChild(int index){
		return getRightChildIndex(index) < size;
	}
	private boolean hasParent(int index){
		return getParentIndex(index) >= 0;
	}

	private int leftChild(int index){
		return items[getLeftChildIndex(index)];
	}
	private int rightChild(int index){
		return items[getRightChildIndex(index)];
	}
	private int parent(int index){
		return items[getParentIndex(index)];
	}


	//swap
	private void swap(int indexOne, int indexTwo){
		int temp = items[indexOne];
		items[indexOne] = items[indexTwo];
		items[indexTwo] = temp;
	}

	//ensureExtraCapacity
	private void ensureExtraCapacity(){
		if (size == capacity){
			items = Arrays.copyOf(items, capacity*2);
			capacity = capacity*2;
		}
	}//ensureExtraCapacity

	//peek
	public int peek(){
		if (size == 0)
			throw new IllegalStateException();

		return items[0];
	}//peek

	//poll -- To remove
	public int poll(){
		if (size == 0)
			throw new IllegalStateException();

		/*Stuff......*/
		int item = items[0];
		items[0] = items[size-1];
		size--;
		heapifyDown();

		return item;
	}//poll


	// add -- To insert
	public void add(int item){
		ensureExtraCapacity();
		items[size] = item;
		size++;
		heapifyUp();

	}

	//heapifyUp
	public void heapifyUp(){
		int index = size - 1;
		while (hasParent(index) && parent(index) > items[index]){
			swap(getParentIndex(index), index);
			index = getParentIndex(index);
		}//while

	}

	//heapifyDown
	public void heapifyDown(){
		int index = 0;
		while (hasLeftChild(index)){
			int smallerChildIndex = getLeftChildIndex(index);
			if (hasRightChild(index) && rightChild(index) < leftChild(index)){
				smallerChildIndex = getRightChildIndex(index);
			}//if

			if (items[index] < items[smallerChildIndex]){
				break;
			}else{
				swap(index, smallerChildIndex);

			}//else
			index = smallerChildIndex;
		}//while

	}

    public void sort()
    {
        int n = size;

        // One by one extract an element from heap
        for (int i=n-1; i>=0; i--)
        {
            // Move current root to end
            swap(0, i);
			size--;
            heapifyDown();

            //System.out.println(Arrays.toString(items));
        }
        size = n;
    }

	public void printHeap(){
		String s = "";
		for (int i = 0; i < size; i++){
			s = s + items[i] + "  ";
		}
		System.out.println(s.trim());
	}//printHeap

	public static void main(String args[]){
		MinIntHeapSort mih = new MinIntHeapSort();

		mih.add(10);
		mih.add(12);
		mih.add(1);
		mih.add(5);
		mih.add(9);
		mih.add(15);
		mih.add(11);
		mih.add(3);


		mih.printHeap();

		//System.out.println(mih.peek());
		//System.out.println(mih.poll());

		mih.printHeap();

		//mih.sort();

		mih.printHeap();

		//*
		mih.add(18);
		mih.add(17);
		mih.add(19);
		mih.add(8);
		//*/
		//System.out.println("size = " + mih.size);

		mih.sort(); // You can only sort once or you need to reform an exactly minHeap before sort
		mih.printHeap();

	}//main


}//MinIntHeap