
public class Heap {
	
	private int []array;
	private int size;
	
	public Heap(int size) {
		array  =new int[size];
	}
	
	public void print(){
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
		
	}
	
	public boolean insert(int data){
		if(++size >= array.length)
			return false;
		
		array[size]=data;
		
		reBubule();
		
		return true;
	}

	private void reBubule() {
	
		if(parent(size) == -1 || parent(size) == 0)
			return;
		
		int pos= size;
	
	
		while(array[parent(pos)] < array[pos] ){
			
			swap(parent(pos),pos);
		
			pos = parent(pos);
	
			if(pos == 1)
    			return;
						
		}
		
	}
	
	public int deque(){
		int temp = array[1];
		array[1] = array[size];
		--size;
		
		maxHeapify(this.array,1);
		
		return temp;
	}
	
	
	
	public void maxHeapify(int []array,int index) {
		
		int left = left(index);
		int right = right(index);
		int max;
		
		if(left != -1 && array[left] > array[index])
			max = left;
		
		else
			max = index;
		
		if(right != -1 && array[right] > array[max])
			max = right;
		
		if(max != index){
			swap(index, max);
			
			maxHeapify(array,max);
		}
		
	}
	
	
	public void buildHeap(int []array){
		
		for(int i = array.length/2 ; i >= 1 ; --i){
			maxHeapify(array, i);
		}
		
	}
	
	boolean isHeap(int arr[], int i, int n)
	{
	   // If a leaf node
	   if (i > (n - 2)/2)
	       return true;
	 
	   // If an internal node and is greater than its children, and
	   // same is recursively true for the children
	   if (arr[i] >= arr[2*i + 1]  &&  arr[i] >= arr[2*i + 2] &&
	       isHeap(arr, 2*i + 1, n) && isHeap(arr, 2*i + 2, n))
	       return true;
	 
	   return false;
	}
	boolean isHeap(int arr[],  int n)
	{
	    // Start from root and go till the last internal
	    // node
	    for (int i=0; i<=(n-2)/2; i++)
	    {
	        // If left child is greater, return false
	        if (arr[2*i +1] > arr[i])
	                return false;
	 
	        // If right child is greater, return false
	        if (arr[2*i+2] > arr[i])
	                return false;
	    }
	    return true;
	}
	public void heapSort(){
	
		for (int i = size; i >= 2; --i) {
			swap(1,i);
			--size;
			maxHeapify(array, 1);
		}
	}
	
	

	private void swap(int parent, int pos) {
		int temp = array[parent];
		array[parent] = array[pos];
		array[pos] = temp;
	}

	public int parent(int index){
		return index/2 < array.length ? index/2 : -1;
	}
	public int left(int index){
		return index*2 < array.length ? index*2 : -1;
	}
	public int right(int index){
		return index*2+1 < array.length ? index*2+1 : -1;
	}

}
