Java’s PriorityQueue

Java’s PriorityQueue, in java.util, is a binary heap, like our ArrayHeap. It has no changePriority. A program that needs to change a priority has two options.

The first option is to take the item out and add it back with the new priority. Java’s PriorityQueue has a remove(Object) that removes a given element from anywhere in the heap. But it has no index map, so it finds the element with a linear search through the heap’s array. That is the $O (n)$ search from earlier in this chapter: the heap’s array is not sorted, so the only way to find an item is to look at every slot.

The second option is to leave the old copy in the queue and add the item again with the new priority. That is one add, which is $O (lo g n)$ . The old copy comes out of the queue later, and the program skips it then.

Adding the patient again

Let’s try the second option on the emergency room. Java’s PriorityQueue has a constructor that takes a comparator, as ArrayHeap(Comparator) did in the binary heap chapter. So the queue can hold pairs of a name and a triage level, ordered by level:

public class Entry {
  String name;
  int level;
  // constructor not shown
}

public class LevelComparator implements Comparator<Entry> {
  @Override
  public int compare(Entry a, Entry b) {
    return Integer.compare(a.level, b.level);
  }
}

Jane arrives at level 4 and Bob at level 2. Then Jane gets worse, and the nurse re-triages her to level 1. The program adds Jane again:

PriorityQueue<Entry> er = new PriorityQueue<>(new LevelComparator());
er.add(new Entry("Jane", 4));
er.add(new Entry("Bob", 2));
er.add(new Entry("Jane", 1));  // Jane's condition worsens

Jane is now in the queue twice:

  Jane (1)  ◄── next out
  Bob  (2)
  Jane (4)

Her level-1 copy is the most urgent, so she is called first and treated. Bob is next. Then the level-4 copy of Jane reaches the front, but Jane has already been treated.

In the waiting room

This also happens in a real emergency room. A nurse calls the next name on the list, and nobody stands up. The patient was taken back to a treatment room earlier, because a nurse noticed that the patient was getting worse. The front desk confirms it, and the nurse crosses the name off the list and calls the next one.

Keeping track of treated patients

To skip old copies systematically, the program keeps a second structure next to the queue: a set of the patients who have already been treated. This is the same idea as the visited array in the maze chapter. There, the search marked each cell it had started from, so that it would not search from that cell again. Here, the program marks each patient it has called, so that it does not call that patient again.

PriorityQueue<Entry> er = new PriorityQueue<>(new LevelComparator());
Set<String> treated = new TreeSet<>();

The program calls the next patient with this method, which takes the queue and the set:

// Removes the next patient to treat and returns their name.
public static String callNext(PriorityQueue<Entry> er, Set<String> treated) {
  while (!er.isEmpty()) {
    Entry next = er.remove();  // Java's remove also returns the element
    if (!treated.contains(next.name)) {
      treated.add(next.name);
      return next.name;
    }
    // an old copy of a patient who was already treated; skip it
  }
  throw new NoSuchElementException();
}

The set is Java’s TreeSet, which is built on a balanced search tree like our TreeMap, so contains and add are $O (lo g n)$ .

The set holds names, not patients. Jane’s two copies have different levels. Suppose the set held Patient objects that compare by triage level, as Patient did in the priority queue chapter. Then a level-1 patient who is not Jane would count as a match for Jane’s level-1 copy. To find Jane in the set, a Patient would need equals to compare names while compareTo compares levels, and the two would disagree. This is the split from the start of this chapter: the name is the item, and it does not change, while the level is the priority, and it can.

The limits

This approach works only when a patient gets worse, which is a decrease-key. Suppose instead Jane gets better, and the nurse moves her from level 1 to level 4. Her level-1 copy is still in the queue, and it is more urgent than the new copy. It comes out first, and Jane has not been treated yet, so the set does not skip it. Jane is called ahead of patients who are now more urgent than she is.

The queue’s size counts the old copies too. In the example above, er.size() is 3, but only two patients are waiting.

peek can return an old copy of a patient who has already been treated. So a program that peeks has to skip old copies too, the same way callNext does.

The heap also grows by one entry for each re-triage. Say $n$ patients are waiting and there have been $k$ re-triages. The heap can hold up to $n + k$ entries, so add and remove cost $O (lo g (n + k))$ instead of $O (lo g n)$ .

The IndexedArrayHeap has none of these limits. It changes the priority in place, so each item is in the heap exactly once.