//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//Min-heap
//Description: An ArrayList based Min-heap class for performing heapSort.
//CS 284
//Programmed by Jonathan Voris
//4/12/06
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import java.util.ArrayList;

public class MinHeap
{
	private ArrayList heapArray;

	public MinHeap()
	{
		heapArray = new ArrayList();
	}

	public MinHeap(Object[] objects)
	{
		this();
		for (int i = 0; i < objects.length; i++)
		{
			heapArray.add(objects[i]);
		}
		//We only need to heapify the first half of the
		//heap array because the second half is all the
		//leaf nodes, which don't have any children
		//that could be larger than they are.
		for (int i = heapArray.size()/2; i >= 0; i--)
		{
			heapifyUp(i);
		}
	}

	//An object comparison function for simplifying the
	//comparisons performed in the heapify methods.
	public static boolean less(Object obj1, Object obj2)
	{
		if (((Comparable)obj1).compareTo(obj2) < 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	//This getter for the internal heap array is for
	//testing purposes.
	public ArrayList getHeapArray()
	{
		return heapArray;
	}

	public Object getMin()
	{
		return heapArray.get(0);
	}

	//Removemin swaps the root node with the last leaf node
	//to perserve heap completeness, then removes the old
	//root. heapifyDown is then called to move the new root
	//node down to correct the heap ordering. Finally, the
	//original root is returned.
	public Object removeMin()
	{
		Object min = heapArray.get(0);
		heapArray.set(0, heapArray.get(heapArray.size()-1));
		heapArray.remove(heapArray.size()-1);
		heapifyDown(0);
		return min;
	}

	//heapifyDown corrects heap ordering caused by removing the root node
	//by bubbling larger values down the heap.
	public void heapifyDown(int index)
	{
		int leftIndex = index*2 + 1;
		int rightIndex = index*2 + 2;
		//assume the current node is smaller than its children
		int indexOfSmallest = index;

		//If the current node has a left child, check if it is smaller than the current node and
		//change the smallest index if need be.
		if ((leftIndex < heapArray.size()) && (less(heapArray.get(leftIndex), heapArray.get(indexOfSmallest))))
		{
			indexOfSmallest = leftIndex;
		}

		//Ditto for the right child
		if ((rightIndex < heapArray.size()) && (less(heapArray.get(rightIndex), heapArray.get(indexOfSmallest))))
		{
			indexOfSmallest = rightIndex;
		}

		//Was one of the children smaller than the current node?
		if (indexOfSmallest != index)
		{
			//If so, swap them and recursively heapify down the correct branch of the heap.
			Object temp = heapArray.get(index);
			heapArray.set(index, heapArray.get(indexOfSmallest));
			heapArray.set(indexOfSmallest, temp);
			heapifyDown(indexOfSmallest);
		}
	}

	//Insert adds the new element to the end of the heap for completeness
	//and calls heapify on the new node's parent to get it in the correctly
	//ordered position.
	public void insert(Object obj)
	{
		heapArray.add(obj);
		heapifyUp((heapArray.size()-2)/2);
	}

	//heapifyUp corrects heap ordering caused by adding new nodes
	//by bubbling smaller values up the heap.
	public void heapifyUp(int index)
	{
		int leftIndex = index*2 + 1;
		int rightIndex = index*2 + 2;
		int indexOfSmallest = index;

		if ((leftIndex < heapArray.size()) && (less(heapArray.get(leftIndex), heapArray.get(indexOfSmallest))))
		{
			indexOfSmallest = leftIndex;
		}

		if ((rightIndex < heapArray.size()) && (less(heapArray.get(rightIndex), heapArray.get(indexOfSmallest))))
		{
			indexOfSmallest = rightIndex;
		}

		if (indexOfSmallest != index)
		{
			Object temp = heapArray.get(index);
			heapArray.set(index, heapArray.get(indexOfSmallest));
			heapArray.set(indexOfSmallest, temp);
			//heapifyUp is exactly the same as heapifyDown, except it recursively
			//works in the opposite direction.
			heapifyUp((index-1)/2);
		}
	}

	//Heapsort sorts the contents of the heap by removing the
	//minimum element until the heap is empty.
	public ArrayList Heapsort()
	{
		ArrayList sorted = new ArrayList();
		while (heapArray.size() > 0)
		{
			sorted.add(removeMin());
		}
		return sorted;
	}
}