import java.util.*;

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

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

	//Insert a new value, Time O(logn), Space O(1), n is number of items in heap
	public void insert(T value) {		
		if (length == maxSize) {
			System.out.println("heap is full, cannot insert " + value);
			return;
		}
		heap[length]= value;
		heapUp(length);
		length++;
	}
	
	//Time O(logn), 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 max (first one), Time O(logn), Space O(1)
	public T remove() {	
		if (length == 0) { 
			System.out.println("heap is empty");
			return null;
		}
		T max = heap[0];
		heap[0] = heap[length-1]; //put last at first
		length--;		
		heapDown(0);		
		return max;
	}
	
	//Time O(logn), 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 O(n)
	public List<T> preorder() {		
		List<T> list = new ArrayList<>();
		preorderRec(0, list);
		return list;
	}
	
	//Recursion helper, Time O(n), Space O(n)
	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 O(n)
	public List<T> inorder() {		
		List<T> list = new ArrayList<>();
		inorderRec(0, list);
		return list;
	}
	
	//Recursion helper, Time O(n), Space O(n)
	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 O(n)
	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) {			
		MaxHeap<Integer> maxHeap = new MaxHeap<>(10);  //capacity 10
		maxHeap.insert(5);           
		maxHeap.insert(4);
		maxHeap.insert(8);
		maxHeap.insert(2);
		maxHeap.insert(7);
		maxHeap.insert(9);
		maxHeap.insert(2);
		maxHeap.insert(10);
		maxHeap.insert(6);

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