No, a FIFO queue cannot do that. It needs a priority queue, one that always hands out the highest-priority item next.
Arrival order and importance order are simply different orders, and lesson 5-2's queue was built to enforce the first one. A patient who arrives last with chest pain has to be served before a patient who arrived an hour earlier with a cough.
Reordering the queue on every arrival is not the answer either, since that is the O(n) shifting problem again.
A priority queue serves by importance instead, and this lesson builds its engine: the heap.
One weak promise, huge payoff
Keeping the waiting list fully sorted would work, but inserting into a sorted array is O(n) shifting, as lesson 2-3 established. The insight behind the heap is that the whole line never needs to be sorted, because only the next item is ever asked for.
A min-heap is a binary tree that keeps exactly one promise, the heap property.
Every node is ≤ its children.
That is much weaker than sorted, and the weakness is where the speed comes from. Nothing says the left child is smaller than the right, and two items at the same level have no defined relationship at all.
The root, however, must be the minimum of everything. Any path down from the root only ever moves to larger values, so no value anywhere in the tree can be smaller than the one at the top.
A heap also fixes its shape, which is not optional. Lesson 7-3 just showed a tree's height degrading to O(n), so a promise about values alone would not be enough.
A heap is always a complete tree: every level is completely full except possibly the bottom one, and the bottom fills strictly left to right with no gaps. Completeness pins the height, because each full level doubles the node count as 1 + 2 + 4 + …, so n nodes can never stack more than about log₂ n levels and the tall chain that ruined the sorted-input BST is structurally impossible.
The three operations follow from those two rules.
- Peeking at the minimum is O(1), since it is just reading the root.
- push places the value in the first free slot on the bottom level, keeping the tree complete, then swaps it upward while it beats its parent, which is O(log n) swaps, at most one per level.
- pop removes the root, moves the last item into its place, and swaps it downward until the promise holds again, also O(log n).
One engineering gem comes free with completeness. No gaps means the tree can live in a plain array with no pointers at all: read the levels top to bottom, left to right, into consecutive slots. The node at index i then has children at 2i+1 and 2i+2, an address formula in the spirit of lesson 2-1.
heapq on a plain list
Python's heap lives in the heapq module and operates on an ordinary list.
import heapq nums = [7, 2, 9, 4, 1, 8, 3] heapq.heapify(nums) print("heap list:", nums) print("smallest:", nums[0]) print("popped:", heapq.heappop(nums)) print("new smallest:", nums[0])
Output
heap list: [1, 2, 3, 4, 7, 8, 9] smallest: 1 popped: 1 new smallest: 2
heapify rearranges the list into heap order in place, and it does so in O(n), which is cheaper than the O(n log n) of sorting it.
There is no heap object anywhere. The list is the heap, laid out exactly as the figure's array, and the module's functions are what maintain the property.
The printed list happens to come out ascending for this input, which is a coincidence of these seven values rather than a rule. Heap order only guarantees each node ≤ its children, so [1, 2, 3, 5, 4] would be a perfectly valid heap.
What is guaranteed is index 0. Before and after the pop, nums[0] holds the minimum, which is the one thing every heap operation preserves.
The emergency room
Each patient is an (urgency, name) tuple, pushed on arrival and popped by urgency.
import heapq arrivals = [(3, "cough"), (1, "chest pain"), (2, "broken arm"), (1, "head injury")] waiting = [] for item in arrivals: heapq.heappush(waiting, item) while waiting: urgency, patient = heapq.heappop(waiting) print(urgency, patient)
Output
1 chest pain 1 head injury 2 broken arm 3 cough
Tuples are what make this work with no extra code. Python compares them element by element, so the urgency number decides the order and the heap needs to know nothing about patients.
The output ignores arrival order completely. Chest pain arrived second and left first, while the cough arrived first and left last, which is the behavior a FIFO queue could not produce.
The two urgency-1 patients tie on the number, so the comparison falls through to the second element and breaks the tie alphabetically, putting chest pain before head injury. That is a side effect of tuple comparison rather than a heap guarantee, and a heap makes no promise about equal-priority items.
Draining the whole heap like this costs O(n log n) in total, which is the same order as sorting. The heap's advantage is not the drain, it is that pushes and pops can interleave, so new patients can arrive mid-drain and still be served in the right place.
A heap's pop is O(log n) because repairing the heap property walks only one root-to-leaf path, and a complete tree is about log₂ n tall.
The repair itself is mechanical. After the root leaves, the last element in the array moves to the top, then swaps downward with its smaller child until it is no longer larger than either one.
Each of those swaps drops one level, so the work is one comparison-and-swap per level rather than a pass over the data. Nothing to the side of that path is ever examined, which is what keeps the other nodes out of the cost.
The level count is where completeness earns its keep. A complete tree with n nodes has about log₂ n levels, the same halving arithmetic from lesson 1-3, and because a heap is always complete that bound holds no matter what order values arrived in.