The Emergency Room

In a busy emergency room, patients are not seen in the order they arrived. Someone who comes in with chest pain is taken ahead of someone who has been waiting an hour with a sprained wrist. When a nurse assesses each new arrival, they assign a triage level: a number that records how urgent the case is, say 1 for the most critical and 5 for the least. The next patient a doctor sees is always the one with the most urgent level.

We already know enough to build this. We can keep the waiting patients in an ArrayList, each tagged with a triage level, and add every new arrival to the end. When a doctor becomes free, we search the list for the patient with the most urgent level, remove that one, and send them in. This works, but every time a doctor is free, we have to search the whole list ourselves.

With the stack and the queue, we gave up the freedom to remove whichever element we liked. A stack always returns the most recently added element. A queue always returns the element that has waited longest. In return, each structure tracks which element that is, so we never had to search for it. We want the same thing here with a different rule: a structure that always returns the most urgent element.

The same need comes up whenever the next thing to handle is the most important one rather than the first or last to arrive. An operating system runs an active program, such as a video player, ahead of a background update. A router sends real-time voice traffic ahead of a large file download. A support system moves tickets from premium customers or from severe failures to the front of an agent’s queue.

In this chapter, we will look at a data structure called a priority queue, which is designed for exactly this. You add elements and take them out, and the one that comes out is the one with the highest priority.