PriorityQueue Interface

Here is an interface for the PriorityQueue ADT.

/**
 * Priority Queue of ordered values.
 *
 * @param <T> Element type.
 */
public interface PriorityQueue<T extends Comparable<T>> {
  /**
   * Insert a value.
   *
   * @param t Value to insert.
   */
  void insert(T t);

  /**
   * Remove best value.
   *
   * @throws EmptyException If queue is empty.
   */
  void remove() throws EmptyException;

  /**
   * Return best value.
   *
   * @return best value in the queue.
   * @throws EmptyException If queue is empty.
   */
  T best() throws EmptyException;

  /**
   * Check if no elements present.
   *
   * @return True if queue is empty, false otherwise.
   */
  boolean empty();
}

Notice the elements of PriorityQueue must be Comparable.

By default, a PriorityQueue will order (prioritize) the elements based on their natural ordering.

The best can be defined to return the largest (maximum) or smallest (minimum) value. By contract, we define best to return the largest value.

Any implementation of PriorityQueue must provide two constructors: a default constructor (with no argument) and a non-default one which allows a Comparator to be provided to overwrite the natural ordering of the element types.

As a further clarifying point, recall a queue is not a set, so duplicate values are allowed.