import java.util.*;

public class MinHeap<T extends Comparable<T>>  {
	T[] heap;
	int length;
	int maxSize;

	//Time O(1) Space O(1)
	@SuppressWarnings("unchecked")
	public MinHeap(int capacity) {
		maxSize = capacity;
		heap = (T[]) new Comparable[capacity]; 
		length = 0; // means queue is empty
	}

	//Insert a new value, Time O(h), Space O(1), n is number of items in heap
	//h is height of heap (complete binary tree) h = log(n)
	public void insert(T value) {		
		if (length == maxSize) {
			System.out.println("heap is full, cannot insert " + value);
			return;
		}
		heap[length]= value;
		heapUp(length++);
	}
	
	//Time O(h), Space O(1)
	private void heapUp(int pos) {
		int parentPos = (pos-1)/2;
		T value = heap[pos];
		while (pos > 0 && (value.compareTo(heap[parentPos]) < 0)) {
			heap[pos] = heap[parentPos]; 
			pos = parentPos; 
			parentPos= (parentPos-1)/2;
		}
		heap[pos] = value; 
	}

	//Remove from min (first one), Time O(h), Space O(1)
	public T remove() {	
		if (length == 0) { 
			System.out.println("heap is empty");
			return null;
		}
		T min = heap[0];
		heap[0] = heap[length-1]; //last put first
		length--;		
		heapDown(0);		
		return min;
	}
	
	//Time O(h), space O(1)
	private void heapDown(int pos) {
		T item = heap[pos];
		int index;
		while (pos < length/2) {
			int left = 2*pos + 1;
			int right = 2*pos + 2;
			if (right < length && heap[left].compareTo(heap[right]) > 0)
				index = right;
			else
				index = left;
			if (item.compareTo(heap[index]) <= 0)
				break;
			heap[pos] = heap[index];
			pos = index;				
		}
		heap[pos] = item;
	}
    
    //Time O(n), Space O(1), n is number of items in heap
    public boolean search(T key) {
		for (int i = 0; i < length; i++) {
			if (key.compareTo(heap[i]) == 0)
				return true;
		}	
		return false;
    }
    
    //Traverse as array, it is also level order of tree, Time O(n), Space O(n)
	public List<T> levelOrder() {
		List<T> list = new ArrayList<>();
		for (int i = 0; i< length; i++) {
			list.add(heap[i]); 
		}	
		return list;
	}
     
	//Traverse as tree preorder, Time O(n), Space (n)
	public List<T> preorder() {		
		List<T> list = new ArrayList<>();
		preorderRec(0, list);
		return list;
	}
	
	//Recursion helper, Time O(n), Space (h)
	private void preorderRec(int nodeIndex, List<T> list) {		
		if (nodeIndex > length-1) 
			return;
		list.add(heap[nodeIndex]); 
		preorderRec( 2*nodeIndex + 1, list);										
		preorderRec( 2*nodeIndex + 2, list);
	}

	//Traverse as tree inorder, Time O(n), Space (n)
	public List<T> inorder() {		
		List<T> list = new ArrayList<>();
		inorderRec(0, list);
		return list;
	}
	
	//Recursion helper, Time O(n), Space (h)
	private void inorderRec(int nodeIndex, List<T> list) {
		if (nodeIndex > length-1) 
			return;	
		inorderRec(2*nodeIndex + 1, list);						
		list.add(heap[nodeIndex]); 
		inorderRec(2*nodeIndex + 2, list) ;	
	}
	
	//Traverse as tree postorder, Time O(n), Space O(n)
	public List<T> postorder() {		
		List<T> list = new ArrayList<>();
		postorderRec(0, list);
		return list;
	}
	
	//Recursion helper, Time O(n), Space (h)
	private void postorderRec(int nodeIndex, List<T> list) {
		if (nodeIndex > length-1) 
			return;	
		postorderRec(2*nodeIndex + 1, list);								
		postorderRec(2*nodeIndex + 2, list);	
		list.add(heap[nodeIndex]) ; 
	}

	public static void main(String[] args) {			
		MinHeap<Integer> minHeap = new MinHeap<>(10);  //capacity 10
		minHeap.insert(5);           
		minHeap.insert(4);
		minHeap.insert(8);
		minHeap.insert(2);
		minHeap.insert(7);
		minHeap.insert(9);
		minHeap.insert(2);
		minHeap.insert(10);
		minHeap.insert(6);

        System.out.println("size: " + minHeap.length);
        System.out.println("level order: " + minHeap.levelOrder());
        System.out.println("preorder: " + minHeap.preorder());
        System.out.println("inorder: " + minHeap.inorder());
        System.out.println("postorder: " + minHeap.postorder());
        
        //search
        int key = 3;
        System.out.println("has " + key +": " + minHeap.search(key));
        key = 7;
        System.out.println("has " + key +": " + minHeap.search(key));
        
        // remove the maximum value in heap
        System.out.println("\nRemove the min val: " + minHeap.remove());      
        System.out.println("size: " + minHeap.length);
        System.out.println("level order: " + minHeap.levelOrder());
        System.out.println("preorder: " + minHeap.preorder());
        System.out.println("inorder: " + minHeap.inorder());
        System.out.println("postorder: " + minHeap.postorder());
	}
}