The changePriority Operation

In the priority queue chapter, each element supplied its own priority. A Patient implemented Comparable and compared by triage level, and the queue ordered patients by that comparison. Suppose Patient also has a setter for its triage level. Here is the emergency room from the last section:

PriorityQueue<Patient> er = new ArrayHeap<>();
Patient jane = new Patient("Jane", "abdominal pain", 4);
er.add(jane);
// more patients are added

Changing the priority on the patient

Twenty minutes later Jane is worse, and the nurse re-triages her to level 1. The first idea is to change the level on Jane’s object:

jane.setTriageLevel(1);  // Jane's condition worsens

This does not work. When Jane was added, the heap placed her by comparing level 4 against the other patients. Setting the field changes the object, but the heap does not know it happened. Jane stays in a slot chosen for level 4, possibly below patients who are now less urgent than she is. The heap’s order is broken, and peek and remove can return the wrong patient.

So the change has to go through the priority queue.

Changing the priority through the queue

Let’s add an operation that takes the patient whose priority changed:

jane.setTriageLevel(1);
er.update(jane);  // Jane's priority changed; fix her place in the heap

Now the queue knows. To fix the heap, it has to find Jane among the patients it holds. Then it can let her swim up or sink down to the place that matches her new level.

The problem is finding Jane. The queue tells patients apart by comparing them, and a Patient’s natural ordering is its triage level. When the queue looks for Jane, any other patient at level 1 is an equal match, and the queue cannot tell which one is Jane.

To find her, the queue would need a second way to tell patients apart, say by name, that does not change. But then equals compares names while compareTo compares levels. The two would disagree, which is what the generics chapter told us to avoid.

The root of it is that one object is doing two jobs. Jane’s name says who she is, and it never changes. Her level says how urgent she is, and that can change. A single compareTo can express only one of them. So we take the priority out of the element. The item is a fixed identifier, and it is how we tell the queue which element we mean. The priority is a separate value that the queue stores next to the item, and it is the thing we raise or lower.

An explicit priority

The priority queue chapter started with an item added together with a separate priority number. It then set that version aside for Comparable, which is how a priority queue is typically implemented. Now the priority has to be stored separately from the item, so we bring the explicit priority back. To keep the queue general, the priority gets its own type parameter P. The only thing we require of P is that priorities can be compared to one another:

public interface AdaptivePriorityQueue<T, P extends Comparable<P>> {
  void add(T item, P priority);
  T peek();
  void remove();
  void changePriority(T item, P priority);
  boolean contains(T item);
  int size();
}

Each slot of the heap in the ArrayHeap can hold an item together with its priority. We bundle the two in a small Entry:

private static final class Entry<T, P> {
  T item;
  P priority;

  Entry(T item, P priority) {
    this.item = item;
    this.priority = priority;
  }
}

peek, remove, and size work as before, and we keep the convention that a smaller priority value means higher priority.

Two operations are new. changePriority takes the place of update. The queue now holds the priority, so the client passes the new priority to the queue instead of setting it on the item. contains reports whether a given item is in the queue. Both have to find the item among the elements the queue already holds, which none of the earlier operations had to do.

Here is the emergency room again, with each patient’s name as the item:

AdaptivePriorityQueue<String, Integer> er = ...;
er.add("Jane with abdominal pain", 4);
er.add("Bob with a fever", 2);

er.peek();  // "Bob with a fever", level 2, the most urgent so far

er.changePriority("Jane with abdominal pain", 1);  // Jane's condition worsens
er.peek();  // "Jane with abdominal pain", now level 1 and ahead of Bob

Raising and lowering a priority

Jane’s priority went from 4 to 1, a smaller number, which under our convention makes her more urgent. Making an item more urgent means decreasing its priority, and making it less urgent means increasing it. The two directions have standard names: lowering the value to raise the priority is a decrease-key, and raising the value to lower the priority is an increase-key.

Some libraries offer the two as separate methods. We keep a single changePriority. The queue holds the old priority, so it can compare the new priority with the old one. If the new value is smaller, the item swims up. If the new value is larger, the item sinks down.