/********************************************************************/
/* Barebones Heap class written during the lecture of Feb 6         */
/* author Suprakash Datta                                           */
/* Disclaimer: This is not meant to be well-designed or have good   */
/*             style. It is meant to highlight some aspects of data */
/*             structures and recursion                             */
/********************************************************************/

public class Heap {
	// Heap will hold non-negative integers only
	// for simplicity I am using a fixed size array
	private int H[] = new int[1024];
	//size of the heap, not to be confused with the length of the array
	private int size; 
	
	public Heap(int sz) { //initializes heap with -1
		size = sz;
		for(int i=0; i < H.length; i++)
			H[i] = -1;
	}
	
	//returns location of the parent of node n
	public static int parent(int n) {
		return (int) ((n-1)/2);
	}
	
	//returns location of the left child of node i
	public static int leftchild(int i) {
		return 2*i+1;
	}
	
	//returns location of the right child of node i
	public static int rightchild(int i) {
		return 2*i+2;
	}
	
	public void printHeap() {
		for(int i = 0; i < this.size; i++)
			System.out.print("  " + H[i]);
		System.out.println();
	}
	
	//returns the height of the heap
	public int heightHeap() {
		if (this.size==0) return 0;
		else return 1+ (int)(Math.log(this.size)/Math.log(2.0));
	}
	
	//method to restore heap property in a heap where there is a
	//single node violating the heap property and with respect to 
	//its children. This method propagates a node down the tree
	//precondition: both children are valid heaps
	
	public void downHeap(int i) {
		int tmp, index;
		
		if(leftchild(i) >=size) return;
		else if(rightchild(i) >= size) {
			if(H[i]>H[leftchild(i)]) {// there is a violation
				tmp = H[i];
				H[i]= H[leftchild(i)];
				H[leftchild(i)] = tmp;
				//keep checking at lower levels and possibly moving values
				downHeap(leftchild(i));
			}
		}
		else {
			if(H[leftchild(i)] == Math.min(H[leftchild(i)], H[rightchild(i)]))
				index = leftchild(i);
			else index = rightchild(i);
			//swap i, index if needed
			if(H[i]>H[index]) {// there is a violation
				tmp = H[i];
				H[i]= H[index];
				H[index] = tmp;
				downHeap(index);//keep checking at lower levels and possibly moving values
			}
			
		}
	}
	
	//method to restore heap property in a heap where there is a
	//single node violating the heap property and with respect to 
	//its parent. This method propagates a node up the tree
	//precondition: both children are valid heaps
	
	public void upHeap(int n) {
		int tmp;
		while(parent(n)>=0) {
			if(H[n]<H[parent(n)]) {
				//swap n, parent(n)
				tmp = H[n];
				H[n] = H[parent(n)];
				H[parent(n)] = tmp;
				n = parent(n);
			}
			else return;
		}
	}
	
	//transform a general array to a heap, bottom up
	public void buildHeap() {
		for(int i= size -1; i>=0; i--)
			downHeap(i);
	}
	
	// add a node to a heap and restore heap property
	public void add(int m) {
		H[size] = m;
		++size;
		upHeap(size-1);
	}
	
	// delete a node from a heap and restore heap property
	public int removeMin() {
		int retval = H[0];
		
		H[0] = H[size-1];
		--size;
		downHeap(0);
		return retval;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}