When a Priority Changes

We built the binary heap two chapters ago, and it did everything the priority queue needed: add and remove in $O(\log n)$, peek in $O(1)$, and no operation that costs $O(n)$. But all of that assumes one thing: once an element is in the queue, its priority never changes.

Go back to the emergency room example from the priority queue chapter. When a patient arrives, a nurse assigns a triage level that records how urgent the case is, and the queue serves the most urgent patient first. But a person’s condition is not fixed at arrival. Someone who checks in with abdominal pain at level 4 can get worse while waiting. Twenty minutes later it is clearly serious, the nurse re-triages them to level 1, and now they must be seen ahead of everyone the old level had put in front of them.

None of our operations can do that. add only puts in a new element, and peek and remove only reach the single highest-priority element. We could try to get the same effect by taking the patient out and adding them back at the new level. But remove does not let us choose whom it takes; it always takes out the highest-priority patient. To reach one particular patient we would have to remove others until that patient reached the top, then add all of them back. That is a lot of work to change the priority of one element.

The same need shows up wherever priorities are assigned when an element arrives but do not stay fixed afterward. An operating system may raise a background job’s priority when a user brings it to the foreground. A delivery service re-ranks the orders already waiting as traffic and kitchen times change. In each case an element that is already in the queue needs a new priority, sometimes higher and sometimes lower, and the queue has to move it to the position that matches its new priority.

So we give the priority queue one more operation, changePriority.