import java.util.*;

public class HeapPriorityQueue implements PriorityQueue
{
  private static final int DFLT_CAPACITY = 1024;
  private Object items[];
  private int numItems;
  private Comparator comparator;

  public HeapPriorityQueue()
  {
    this(DFLT_CAPACITY, null);
  }

  public HeapPriorityQueue(Comparator c)
  {
    this(DFLT_CAPACITY, c);
  }

  public HeapPriorityQueue(int initialCapacity)
  {
    this(initialCapacity, null);
  }

  public HeapPriorityQueue(int initialCapacity, Comparator c)
  {
    items = new Object[initialCapacity + 1];
    comparator = c;
  }

  public boolean isEmpty()
  {
    return numItems == 0;
  }

  public Object peekMin()
  {
    if (numItems == 0)
    {
      throw new NoSuchElementException();
    }

    return items[1];
  }

  public Object removeMin()
  {
    if (numItems == 0)
    {
      throw new NoSuchElementException();
    }

    Object min = items[1];
    items[1] = items[numItems];
    numItems--;
    reheapDown();
    return min;
  }

  public void add(Object obj)
  {
    numItems++;
    if (numItems >= items.length)
      doubleCapacity();
    items[numItems] = obj;
    reheapUp();
  }

  private boolean lessThan(Object obj1, Object obj2)
  {
    if (comparator != null)
      return comparator.compare(obj1, obj2) < 0;
    else
      return ((Comparable)obj1).compareTo(obj2) < 0;
  }

  private void reheapDown()
  {
    Object root = items[1];  // save root
    int iParent = 1, iChild = 2;

    while (iChild <= numItems)
    {
      if (iChild < numItems && lessThan(items[iChild+1], items[iChild]))
        iChild++;  // set iChild to the smaller right child
      if (!lessThan(items[iChild], root))
        break;
      items[iParent] = items[iChild];
      iParent = iChild;
      iChild = 2 * iParent; // left child
    }
    items[iParent] = root;
  }

  private void reheapUp()
  {
    Object temp = items[numItems];  // save new leaf
    int iChild = numItems, iParent = iChild / 2;

    while (iParent >= 1 && lessThan(temp, items[iParent]))
    {
      items[iChild] = items[iParent];
      iChild = iParent;
      iParent = iChild / 2;
    }
    items[iChild] = temp;
  }

  private void doubleCapacity()
  {
    Object tempItems[] = new Object[2 * items.length - 1];
    for (int i = 0; i <= numItems; i++)
      tempItems[i] = items[i];
    items = tempItems;
  }
  
  // consider adding the following:
  public int getSize()
  {
	  return numItems;
  }
  public String toString()
  {
	  String s = "";
	  int c = 1;
	  while (c <= numItems)
	  {
		  s += items[c];
		  c++;
	  }
	  return s;
  }
  public void traverseInOrder ()
  {
	  traverseInOrder(1);
  }
  public void traverseInOrder (int k)
  {
	  if (k>getSize())
		  return;
	  else
	  {
		  traverseInOrder(k*2);
		  System.out.println(items[k]);
		  traverseInOrder(k*2+1);
	  }
  }
  // note traverseInOrder is like #4/p189 but not identical.  Why?  
}