package heap;

//BinaryHeap class

//CONSTRUCTION: with optional capacity (that defaults to 100)

//******************PUBLIC OPERATIONS*********************
//void insert( x )       --> Insert x
//AnyType deleteMin( )--> Return and remove smallest item
//AnyType findMin( )  --> Return smallest item
//boolean isEmpty( )     --> Return true if empty; else false
//boolean isFull( )      --> Return true if full; else false
//void makeEmpty( )      --> Remove all items
//******************ERRORS********************************
//Throws Overflow if capacity exceeded

/**
 * Implements a binary heap.
 * Note that all "matching" is based on the compareTo method.
 * 
 * @author Mark Allen Weiss
 * @author Li Hongyang
 */
public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {

        void replaceBy(int p, AnyType newValue) {
	    if (p <= 0 || p > currentSize)
		throw new IllegalArgumentException();
	    else {
		int compResult = array[p].compareTo(newValue);
		array[p] = newValue;
		if (compResult < 0) 
		    percolateDown(p);
		else if (compResult > 0)
		    percolateUp(p);
	    }
	}
	
	/**
	 * Construct the binary heap.
	 */
	public BinaryHeap() {
		this(DEFAULT_CAPACITY);
	}

	/**
	 * Construct the binary heap.
	 * 
	 * @param capacity 
	 * 				the capacity of the binary heap.
	 */
	public BinaryHeap(int capacity) {
		currentSize = 0;
		array = (AnyType[]) new Comparable[capacity + 1];
	}

	/**
	 * Insert into the priority queue, maintaining heap order.
	 * Duplicates are allowed.
	 * 
	 * @param x 
	 * 				the item to insert.
	 * @exception Overflow 
	 * 				if container is full.
	 */
	public void insert(AnyType x) throws Overflow {
		if (isFull())
			throw new Overflow();

		// Percolate up
		int hole = ++currentSize;
		for (; hole > 1 && x.compareTo(array[hole / 2]) < 0; hole /= 2)
			array[hole] = array[hole / 2];
		array[hole] = x;
	}

	/**
	 * Find the smallest item in the priority queue.
	 * 
	 * @return the smallest item, or null, if empty.
	 */
	public AnyType findMin() {
		if (isEmpty())
			return null;
		return array[1];
	}

	/**
	 * Remove the smallest item from the priority queue.
	 * 
	 * @return the smallest item, or null, if empty.
	 */
	public AnyType deleteMin() {
		if (isEmpty())
			return null;

		AnyType minItem = findMin();
		array[1] = array[currentSize--];
		percolateDown(1);

		return minItem;
	}

	/**
	 * Establish heap order property from an arbitrary
	 * arrangement of items. Runs in linear time.
	 */
	private void buildHeap() {
		for (int i = currentSize / 2; i > 0; i--)
			percolateDown(i);
	}

	/**
	 * Test if the priority queue is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return currentSize == 0;
	}

	/**
	 * Test if the priority queue is logically full.
	 * 
	 * @return true if full, false otherwise.
	 */
	public boolean isFull() {
		return currentSize == array.length - 1;
	}

	/**
	 * Make the priority queue logically empty.
	 */
	public void makeEmpty() {
		currentSize = 0;
	}

	private static final int DEFAULT_CAPACITY = 100;

	private int currentSize; // Number of elements in heap

	private AnyType[] array; // The heap array

	/**
	 * Internal method to percolate down in the heap.
	 * 
	 * @param hole 
	 * 				the index at which the percolate begins.
	 */
	private void percolateDown(int hole) {
		int child;
		AnyType tmp = array[hole];

		for (; hole * 2 <= currentSize; hole = child) {
			child = hole * 2;
			if (child != currentSize
					&& array[child + 1].compareTo(array[child]) < 0)
				child++;
			if (array[child].compareTo(tmp) < 0)
				array[hole] = array[child];
			else
				break;
		}
		array[hole] = tmp;
	}
	
	/**
	 * Internal method to percolate up in the heap.
	 * 
	 * @param hole 
	 * 				the index at which the percolate begins.
	 */	
	private void percolateUp(int hole) {
		AnyType x = array[hole];
		for (; hole > 1 && x.compareTo(array[hole / 2]) < 0; hole /= 2)
			array[hole] = array[hole / 2];
		array[hole] = x;	
	}

	/**
	 * Check whether an array is a heap implementation
	 * 
	 * @param <AnyType>
	 * 				the type of array elements	 
	 * @param heapArray
	 * 				the array 
	 * @param heapSize
	 * 				the total number of elements in the array
	 * 
	 * @return true if the given array is a heap; false otherwise.
	 */
	public static <AnyType extends Comparable<? super AnyType>> boolean isHeapImplementation(
			AnyType[] heapArray, int heapSize) {
		
		/*
		 * The index i runs through all non-leaf nodes
		 */
		for (int i = 1; i*2 <= heapSize; i++) {
			/*
			 * Obtain the smaller child of the current node
			 */
			AnyType minChild = heapArray[i*2];
			if (i*2+1 <= heapSize && minChild.compareTo(heapArray[i*2+1]) == -1) {
				minChild = heapArray[i*2+1];
			}
			/*
			 * If we find a violation of the min heap property, return false.
			 */
			if (heapArray[i].compareTo(minChild) == 1) {
				return false;
			}
		}
		/*
		 * No violation found. The array is a min heap.
		 */
		return true;
	}
	
	/**
	 * Delete and return the max element of the heap
	 * 
	 * @return
	 * 				the max element of the heap
	 */
	public AnyType deleteMax() {
		int idx = currentSize;
		for (int i = currentSize; i > 0 && i*2 > currentSize; i--) {
			if (array[i].compareTo(array[idx]) == 1) idx = i;
		}		
		
		AnyType ans = array[idx];
		array[idx] = array[currentSize--];
		
		percolateUp(idx);
			
		return ans;
	}

}