/** Realization of a priority queue by means of a heap.  The heap is
  * built upon a vector-based complete binary tree.
  */
public class HeapPriorityQueue implements PriorityQueue { 
  protected CompleteBinaryTree T;
  protected Comparator comp;
  /** Inner class for heap entries. */
  protected static class  MyEntry implements Entry {
    protected Object key, value;
    public MyEntry(Object k, Object v) { key = k; value = v; }
    public Object key() { return key; }
    public Object value() { return value; }
  }
  /** Inner class for a comparator that uses the natural ordering of keys. */
  protected static class DefaultComparator implements Comparator {
    public DefaultComparator() { /* default constructor */ }
    public int compare(Object a, Object b) throws ClassCastException { 
      return ((Comparable) a).compareTo(b); // use the natural order for a
    }
  }
  /** Creates an empty heap with the default comparator. */ 
  public HeapPriorityQueue() {  
    T = new VectorCompleteBinaryTree(); // use a vector-based tree
    comp = new DefaultComparator();     // use the default comparator
  }
  /** Creates an empty heap with the given comparator. */
  public HeapPriorityQueue(Comparator c) {
    T = new VectorCompleteBinaryTree();
    comp = c;
  }
  /** Returns the size of the heap. */
  public int size() { return T.size(); } 
  /** Returns whether the heap is empty. */
  public boolean isEmpty() { return T.size() == 0; }