/** 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; }