The Adaptive Priority Queue ADT

An adaptive priority queue is a priority queue that also lets the priority of an item change while the item waits in the queue.

Solution

The queue placed the patient according to the old level. Changing the field does not move the patient, so the queue’s order is broken, and peek and remove can return a patient who is not the most urgent.

Solution

The queue tells patients apart only through compareTo, which compares triage levels. Any other patient at the same level is an equal match, so the queue cannot tell which of them is the patient the client changed. An adaptive priority queue takes the priority out of the item. The item is a fixed identifier that tells the queue which element the client means, and the priority is a separate value that the queue stores next to it.

Exercise

Here is the interface of a plain priority queue, where each item supplies its own priority:

public interface PriorityQueue<T extends Comparable<T>> {
  void add(T item);  // adds item
  T peek();          // returns the highest-priority item
  void remove();     // removes the highest-priority item
  int size();        // returns the number of items
}

Change it into an interface AdaptivePriorityQueue that lets a waiting item’s priority change, with the priority as a type parameter P. Give the interface header and the new and changed signatures.

Solution

The header is:

public interface AdaptivePriorityQueue<T, P extends Comparable<P>>

The queue compares priorities, not items, so the Comparable bound moves from T to P. peek, remove, and size stay the same. These are new or changed:

void add(T item, P priority);             // the priority is now a separate argument
void changePriority(T item, P priority);  // gives a waiting item a new priority
boolean contains(T item);                 // reports whether the item is in the queue

Solution

changePriority(item, priority) names the element to change by its item. If two equal items were in the queue, the call could not tell which one to change. So add rejects an item that is already in the queue.