import java.util.ArrayList;

public class HeapPriorityQueue implements PriorityQueue 
{
	private ArrayList items;
	private int numNodes;
	
	public HeapPriorityQueue()
	{
		items = new ArrayList();
		items.add(null);		// first "real" add should go at index 1
		numNodes = 0;			// numNodes is also index of "last leaf"
	} 

	public void add(Object x)
	{
		items.add(x);
		numNodes++;
		int k = numNodes;
		while (k/2 >= 1 && ((Comparable)items.get(k)).compareTo(items.get(k/2)) < 0)
		{
			Object temp = items.get(k);
			items.set(k,items.get(k/2));
			items.set(k/2,temp);
			k = k/2;
		}
	}
	
	public Object removeMin()
	{
		if (isEmpty())
			throw new java.util.NoSuchElementException("Empty Queue");
		else
		{
			Object min = peekMin();
			items.set(1,items.get(numNodes));
			numNodes--;
			if (numNodes > 1)
				reheap(1);
			return min;
		}
	}
	
	public Object peekMin() 
	{
		if (isEmpty())
			throw new java.util.NoSuchElementException("Empty PQueue");
		
		return items.get(1);
	}
	
	public boolean isEmpty()
	{
		return numNodes == 0;
	}

	public String toString()
	{
		String result= "[";	
		for (int i = 1; i <= numNodes; i++)
		{
			result += items.get(i);
			if (i < numNodes)
				result += ", ";
		}
		return result += "]";
	}
	
	private void reheap(int root)
	{
		int leftChild, rightChild, minChild, curr;
		Object last = items.get(root);
		
		curr = root;
		while (2 * curr <= numNodes)
		{
			// find smaller child, assume left, then check if right also
			// present and smaller
			minChild = leftChild = 2 * curr;
			rightChild = 2 * curr + 1;
			if (rightChild <= numNodes)	// is there a right child?
			{
				// which is smaller, right or left?
				if (((Comparable)items.get(rightChild)).compareTo(items.get(leftChild)) < 0)
					minChild = rightChild;
			}
			
			if (((Comparable)last).compareTo(items.get(minChild)) < 0)
				break;	// finished
			else
			{
				items.set(curr,items.get(minChild));
				items.set(minChild,last);
				curr = minChild;
			}
		}
	}
    
	public static void main(String[] args)
	{
		PriorityQueue q = new HeapPriorityQueue();
		q.add(new Integer(3));
		q.add(new Integer(6));
		q.add(new Integer(24));
		q.add(new Integer(39));
		q.add(new Integer(8));
		q.add(new Integer(25));
		q.add(new Integer(32));
		System.out.println(q);
		q.removeMin();
    	System.out.println(q);
		q.removeMin();
    	System.out.println(q);
    	q.removeMin();
    	System.out.println(q);
    }
} 
