The Priority Queue ADT

Here is the PriorityQueue interface. Priority comes from the natural ordering of the elements: a smaller element has the higher priority.

public interface PriorityQueue<T extends Comparable<T>> {
  void add(T item);
  T peek();
  void remove();
  int size();
}

Solution

A priority queue is a collection where the element with the highest priority is always the next one removed. add inserts an element. peek returns the highest-priority element without removing it. remove takes out the highest-priority element and returns nothing. size returns the number of elements.

Solution

The two removes take out 3 and then 5. peek() returns 7 and size() returns 2.

Solution

Each one throws an exception. In this course, peek and remove throw a NoSuchElementException, and add throws an IllegalArgumentException. add rejects null because null has no natural ordering and cannot be compared with the other elements.

Solution

No, it makes no promise about ties. The client has to build the tie-break into the elements’ compareTo method. For example, compareTo compares arrival times when the priorities are equal.

Solution

The implementation offers a second constructor that takes a Comparator<T> and uses it in place of the natural ordering. A client who passes a comparator that reverses the natural order, where compare(a, b) returns b.compareTo(a), gets a max priority queue.