Solution: Use an Adaptive Priority Queue

The adaptive priority queue has an operation for each kind of event, so each event becomes a call or two:

public static List<String> serveOrder(String[][] events) {
  AdaptivePriorityQueue<String, Integer> pq = new IndexedArrayHeap<>();
  List<String> served = new ArrayList<>();
  for (String[] e : events) {
    if (e[0].equals("add")) {
      pq.add(e[1], Integer.parseInt(e[2]));
    } else if (e[0].equals("change")) {
      pq.changePriority(e[1], Integer.parseInt(e[2]));
    } else {  // "serve"
      served.add(pq.peek());  // the highest-priority task
      pq.remove();
    }
  }
  return served;
}

A serve event reads the top with peek and then takes it out with remove. These are the same two steps the priority queue chapter used to serve a task.

Let’s trace the example. After each event, the diagram shows the waiting tasks in priority order, and peek marks the task that would be served next.

add A 5, add B 3, add C 8: the queue now holds the three tasks in priority order.

┌─────┬─────┬─────┐
│ B:3 │ A:5 │ C:8 │   size = 3
└─────┴─────┴─────┘
   ▲
  peek → B:3   (min)

change C 1: C’s priority drops to 1, which makes C the highest-priority task.

┌─────┬─────┬─────┐
│ C:1 │ B:3 │ A:5 │   size = 3
└─────┴─────┴─────┘
   ▲
  peek → C:1   (min)

serve: the highest priority is C at 1. Served so far: [C].

┌─────┬─────┐
│ B:3 │ A:5 │   size = 2
└─────┴─────┘
   ▲
  peek → B:3   (min)

change A 2: A’s priority drops to 2.

┌─────┬─────┐
│ A:2 │ B:3 │   size = 2
└─────┴─────┘
   ▲
  peek → A:2   (min)

serve: the highest priority is A at 2, ahead of B at 3. Served so far: [C, A].

┌─────┐
│ B:3 │   size = 1
└─────┘
   ▲
  peek → B:3   (min)

serve: only B is left. Served: [C, A, B].

For $m$ events on a queue of up to $n$ tasks, each event does a constant number of queue operations. With the TreeMap index map, each of those operations is $O (lo g^{2} n)$ in the worst case, so the whole run is $O (m lo g^{2} n)$ . A plain priority queue would have to find the task for every change, and that is an $O (n)$ scan. So on a run with many changes, the adaptive queue is much faster. The index map is part of IndexedArrayHeap, so we can replace it with a constant-time map without changing serveOrder. With that map, every event drops to $O (lo g n)$ .