The Priority Queue ADT

In the emergency room, a new patient arrives and we add them along with how urgent they are. A doctor becomes free and we take out the most urgent patient. Sometimes we want to know who is next without sending them in yet, and sometimes we want to know how many are still waiting. These four operations make up the interface.

Here is a first version, written so that each element is added together with a number that says how urgent it is:

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

add puts an item in with its priority, peek returns the highest-priority item without taking it out, remove takes that item out, and size reports how many items are waiting. Like pop and dequeue, remove returns nothing. To see the highest-priority item, call peek; to take it out, call remove.

We will follow the triage convention: a smaller priority number means more urgent, since level 1 is the most critical case. So the highest-priority item is the one with the smallest number. This is only a convention.

A short example:

PriorityQueue<String> er = ...;
er.add("John Doe with chest pain", 1);
er.add("Jane Smith with sprained wrist", 4);
er.add("Bob Johnson with high fever", 2);

er.remove();  // removes "John Doe with chest pain"  — level 1, the most urgent
er.remove();  // removes "Bob Johnson with high fever"  — level 2, the next most urgent

Letting the element supply its own priority

This interface works, but the separate priority number is often redundant, because the element often has an order of its own already. Numbers have a natural order. Timestamps order events from earliest to latest. Even our patients could be objects that are ordered by triage level.

public class Patient implements Comparable<Patient> {
  private String name;
  private String condition;
  private int triageLevel;

  // constructor and other methods not shown for brevity

  @Override
  public int compareTo(Patient other) {
    return Integer.compare(this.triageLevel, other.triageLevel);
  }
}

With elements like these, the queue does not need a separate priority number. We let each element’s natural ordering supply its priority, and make the interface generic over a T that extends Comparable<T>. That gives us the interface we will use for the rest of the chapter:

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

This version is more general than the first one, because the explicit-priority version is a special case of it. Patient shows how: its triage level is a priority number, and its compareTo compares that number. You can use the same idea to order elements by any other criterion.

Operations not in the interface

There is no way to get an element by index, and no notion of first or last by position. The only element you can ever look at or remove is the highest-priority one.

  ┌──────────────────────────────────┐
  │   "sprained wrist" (4)           │
  │          "high fever" (2)        │
  │   "chest pain" (1)  ◄── next out │
  └──────────────────────────────────┘
   any arrangement inside; only the
   highest-priority element is reachable

Reaching that one element quickly is the problem we will spend the rest of the chapter on.