import java.util.Vector;
import java.util.NoSuchElementException;


/*
 * A priority queue based on heaps.  See CLR chapter 7.
 * This gives us the following asymptotic run times:
 * 
 * insert(): O(lg n)
 * get[min](): O(lg n)
 * peek(): O(1)
 * isEmpty(): O(1)
 * size(): O(1)
 * 
 *
 * Because Java indexes arrays starting at 0, our parent/children
 * indices are : parent = (i-1)/2; left = 2*i+1; right = 2*i+2.
 *
 * Note also that since we are using Vectors instead of arrays, we
 * must be careful to only use the constant time Vector operations.
 * Note also that many vector operations will change the indexing of
 * other items in the vector, which would be a Bad Thing.  Thus, we
 * use setElementAt, elementAt, and we insert/remove only at the last
 * element.
 */

/*
 * An implementation of a Priority Queue built using Vector.  Uses the
 * Vector ability to increase capacity automatically; see
 * java.util.Vector
 */

public abstract class PriorityQueue {

  private Vector elements;         // elements of the priority queue
  final int INITIALCAPACITY = 10;  // initial capacity

  // Create a new priority queue; size doubles whenever it gets full
  public PriorityQueue () {
    elements = new Vector(INITIALCAPACITY, 0);
  }

  // Override this method to determine how items are ordered
  // return true iff Object a is before Object b
  abstract public boolean before (Object a, Object b);

  // Insert an element into the priority queue
  public void insert (Object item) {
    int i;

    elements.addElement(item);
    // We now must restore the heap ordering.  At each step, we copy
    // into position i its parent's value.
    i = elements.size()-1;
    while (i > 0 && before(item, elements.elementAt((i-1)/2))) {
      elements.setElementAt(elements.elementAt((i-1)/2), i);
      i = (i-1)/2;
    }
    // Now set the item where it belongs.
    elements.setElementAt(item, i);
  }

  // Check if the priority queue is empty
  public boolean isEmpty () {
    return elements.isEmpty();
  }

  // Return the minimum element in the priority queue
  // throw NoSuchElementException if queue is empty
  public Object peek () {
    if (isEmpty()) throw new NoSuchElementException("PriorityQueue");
    return elements.elementAt(0);
  }

  // Delete the minimum element from the priority queue and return it
  // Note that we cannot follow the standard algorithm and remove the
  // first item, then try to copy the last into its place.  Removing
  // the first item changes the index of all the other Vector entries.
  public Object get () {
    Object item = peek();

    // Copy last item into top slot.
    elements.setElementAt(elements.elementAt(elements.size()-1), 0);
    // Now delete the last item.
    elements.removeElementAt(elements.size()-1);
    heapify(0);
    return item;
  }

  // Restore the heap property at index i, assuming that both of i's
  // children are already heaps.
  private void heapify(int i) {
    int left = 2*i+1;
    int right = 2*i+2;
    int smallest = i;

    if (left < elements.size() &&
        before(elements.elementAt(left), elements.elementAt(i)))
      smallest = left;
    if (right < elements.size() &&
        before(elements.elementAt(right), elements.elementAt(smallest)))
      smallest = right;
    // Swap the smaller of the children with i; (i == smallest) =>
    // parent is smaller than its children
    if (smallest != i) {
      Object temp = elements.elementAt(i);
      elements.setElementAt(elements.elementAt(smallest), i);
      elements.setElementAt(temp, smallest);
      heapify(smallest);
    }
  }

  // Clear the priority queue
  public void clear () {
    elements.removeAllElements();
  }

  // return the current size of the priority queue
  public int size () {
    return elements.size();
  }

  // return a string representation of the priority queue  
  // useful for debugging
  public String toString() {
    return elements.toString();
  }
}