DATA·II Data structures Chapter 18 of 65
Who is next
An emergency room: patients arrive every few minutes, there are two doctors, and deciding whom to call in is up to you. First a plain queue, then a list, then a heap: a tree that lives in an array without a single link. Along the way you will meet Napoleon’s surgeon, who invented triage, the ten strongest earthquakes from a stream, and the event calendar that runs the emergency room itself.
Data structures
- 13 Complexity
- 14 Arrays
- 15 Stacks, queues
- 16 Hash tables
- 17 Trees
- 18 Heaps you are here
- 19 Graphs
Builds on: 17 · A garden of search trees
What you will take away
- keep the most urgent item at hand: a priority queue on a heap and the heapq module
- how a heap lives in an array, and why adding and removing cost O(log n) while building costs O(n)
- find the top k in a stream, merge sorted lists and simulate events with a calendar
The last chapter ended in an emergency room. Patients are brought in one after another, each with their own trouble, and the first to be treated must be whoever is worst off, no matter when they arrived. The search tree from Chapter 17 could handle that: it keeps everyone in order, and the most serious case lies at its edge. But it does work nobody asked for. The dispatcher has no use for the full order, neither the second most serious case nor the hundredth. What the dispatcher needs is one answer to one question, asked again and again while new people keep coming through the door: who is next?
You are about to take the dispatcher’s desk. At first you will make the decisions yourself, then hand them to a program (a queue, then a list and finally a heap), and after every shift you will check two numbers: how long the patients waited and how much work the dispatcher did.
The Rhine, 1792. The worst wounded first
Larrey’s rule is already an algorithm. Every patient has a number, the urgency, and the one to take is the one whose urgency is greatest. The rest is a question of speed: how to find that patient quickly when many are waiting and new ones keep arriving.
The dispatcher’s desk
Below is the emergency room. Patients come in on the left, each carrying a card with a category number: 1 is red, the most urgent, 5 is blue. On the right are two doctors. When a doctor is free, the shift stops and waits for you: tap the patient to call in. Under the room is the score: how long patients of each color waited on average and at the longest. Play for a couple of hours, then switch the dispatcher to a program, “First come” or “By severity,” and compare on the same patients.
If you called the reds and oranges first, your score looks much like the “by severity” mode’s: urgent patients wait minutes, blue ones longer. “First come” treats everyone alike: a red patient waits as long as someone with a splinter, and on a busy day that means dozens of minutes.
The “by severity” mode is easy to turn into a program: keep the waiting patients in some collection and take the most urgent one out of it every time. Such a collection is called a priority queue. Like the stack and the queue from Chapter 15, it is an abstract type, described by its operations rather than by how it is built. There are two operations: add an item with its key, and take out the item with the smallest key. We’ll take “smallest” to mean “most urgent”: the red category is number 1, and that is how the Manchester scale counts too. The question of the chapter is what to build a priority queue out of.
First attempt: a list
We start with an ordinary list. A patient arrives: append, which is $O(1)$. A patient is called: min finds the most urgent one, and remove takes them out. Let the key be the tuple (category, arrival number): tuples are compared by their first element and, on a tie, by the second, as we saw in Chapter 6. Of two patients in the same category, the one who came earlier goes first, which is fair.
An emergency room has ten or twenty people waiting, and a list will cope with that. But a priority queue can be far longer: ambulance calls across a whole big city, jobs on a server, events in a simulation, hundreds of thousands of items. Here is what one patient costs when a thousand, ten thousand and a hundred thousand are waiting.
Tens of microseconds with a thousand, more than a millisecond with a hundred thousand: ten times as many waiting, and every call costs almost ten times as much. This is the linear time of Chapter 13, and the reason is plain: min looks through everyone, and remove searches again and then moves the tail.
What if the list is kept sorted? Then the most urgent patient is always at the front. But taking them out is pop(0), and Chapter 14 showed that this moves everyone else over by a cell. Reverse the order, so that the most urgent stands at the end, and pop() becomes $O(1)$, but now an arrival is expensive: binary search (the bisect module) finds the new patient’s place in $O(\log n)$, yet inserting into the middle moves half the list. One of the two operations is always linear.
| How it is stored | Arrival | Call |
|---|---|---|
| a list as it is | $O(1)$ | $O(n)$ |
| a sorted list | $O(n)$ | $O(1)$ |
| a search tree (Chapter 17) | $O(\log n)$ | $O(\log n)$ |
| a heap (this chapter) | $O(\log n)$ | $O(\log n)$ |
A balanced search tree does both operations in logarithmic time. But it keeps the full order, and order has a price: rotations, pointers, two links per node. Since we don’t need the full order, could we pay less?
The heap: every boss outranks the staff
Think of how an army or a large office is organized. Every boss has a few subordinates, and they have subordinates of their own. We ask for one thing only: every boss must be more urgent than their subordinates. The subordinates of one boss are in no particular order among themselves, and neighboring departments have nothing to do with each other. This single condition already puts the most urgent at the top: anyone else has a boss more urgent than they are.
A binary tree with this condition is a heap: the key of every node is no larger than the keys of its children. Compare it with the search tree from the last chapter. There the order was horizontal: left descendants smaller than the node, right ones larger, and the tree would find anything you asked for. In a heap the order is only vertical: along any path from the root down the keys never decrease, while left and right can be anything. Finding an arbitrary item in a heap is as hard as finding it in a sack. But the smallest is always at the root, and the condition is so weak that keeping it costs almost nothing.
A word of warning about the name. Programmers also say “the heap” for the region of memory where a running program keeps its objects. The two heaps share nothing but the word: this one is a data structure, the other is a way of handing out memory.
A tree without pointers
The second half of the idea is how to store a heap. We fill the tree level by level, top to bottom and left to right on each level, with no gaps. Such a tree is called complete: all its levels are full, except perhaps the last, which fills from the left without holes. Number the nodes in the same order, level by level, starting from zero. The root is 0, its children 1 and 2, their children 3, 4, 5, 6, and so on. Try to guess from the picture how the numbers of a parent and its children are related.
A node numbered $i$ has its children at $2i + 1$ and $2i + 2$ and its parent at $(i - 1) \mathbin{//} 2$. So the tree needs no node objects and no links to children, unlike the trees of Chapter 17: an ordinary list is enough, and the links are computed by arithmetic, like the address of an array cell in Chapter 14. The tree exists only in our heads; in memory there is a solid row of references without a single one to spare.
And we get for free what the last chapter needed rotations for. A complete tree can’t degenerate into a stick: it is always as low as it can be. Its levels hold 1, 2, 4, 8, … nodes, and a heap of $n$ items has $\lfloor \log_2 n \rfloor + 1$ levels. A million items make twenty levels, a billion thirty.
A heap has 20 items. Which cell holds the parent of the item in cell 12, and does cell 12 have children?
$(12 - 1) \mathbin{//} 2 = 5$. The children would be in cells $2 \cdot 12 + 1 = 25$ and $26$, but the last cell is 19, so 12 is a leaf. In general, in a heap of $n$ items the leaves are all the cells from $n \mathbin{//} 2$ on, which is half of them (rounded up when $n$ is odd). This will come in handy.
Sifting
All that remains is to add and remove items without breaking the heap condition. One technique does the job both times: sifting, in which the offender swaps places with a vertical neighbor until order is restored.
Adding. The new item goes into the first free cell, at the end of the list, and the tree stays complete. The condition can now be broken only between the newcomer and its parent. If the newcomer is smaller than its parent, they swap, and we check against the next parent up. The newcomer rises until it meets a parent smaller than itself or becomes the root. This is sifting up.
Drag the slider under the tree. The 1 came fifth: it landed in cell 4 under the 4, swapped with it, then with the 3 at the root, and became the root after two swaps. The resulting list [1, 3, 2, 5, 4, 9, 8] isn’t sorted at all, and it doesn’t need to be: a heap promises only that the smallest comes first.
Taking out. The smallest sits in cell 0, and we hand it over. That leaves a hole, though, and a hole in the middle breaks completeness. So the last item of the list moves into the root: its cell is freed without any shifting, since pop() from the end costs $O(1)$. Now the offender is at the root, and most likely it is larger than its children. We swap it with the smaller child, so that the new parent is no larger than the other child either, and repeat one level down. This is sifting down.
Seven extractions of the smallest gave the numbers in increasing order, so a heap can sort as well; we’ll come back to that. First, the cost of each operation.
In a heap of $n$ items, adding an item and taking out the smallest take at most $2\log_2 n$ comparisons.
Sifting up climbs one level per step and makes one comparison; sifting down sinks one level per step and makes two comparisons, one with each child. A complete tree of $n$ nodes has $\lfloor \log_2 n \rfloor + 1$ levels, so a climb or a descent passes through at most $\lfloor \log_2 n \rfloor$ levels. The swaps, the move of the last item and append cost $O(1)$ per step.
A dispatcher on a heap
You don’t have to write a heap yourself every time: Python already has one, in the heapq module. There is no class there, only functions that work on an ordinary list the way our push and pop do: heapq.heappush(a, x), heapq.heappop(a), and a[0] to peek at the smallest without taking it out. In CPython these functions are written in C. Here is the experiment from the list attempt again, with the same stream of patients, only now the corridor is a heap.
About a microsecond per patient, whether a thousand are waiting or a million. With a hundred thousand the heap beats the list more than a thousandfold. A good part of that time, about a fifth of a microsecond, goes into randint itself, and twenty levels of sifting come to two or three dozen comparisons, a trifle.
Once again a tuple serves as the key, and the arrival number in it is there for a reason. If the heap held pairs (category, name), then on equal categories the tuples would go on to compare names, and red Alice would be called before red Bob, who had arrived an hour earlier. And if instead of a name there is an object that can’t be compared, such as a dictionary with the patient’s card, heappush fails with a TypeError. An arrival counter cures both troubles: it is unique, so the comparison never gets as far as the third element.
One more detail of heapq: its heap has the smallest on top. If you need the largest (say the key is “severity,” where 10 is worse than 1), push the key with a minus sign: heappush(a, (-severity, number, card)). The most severe case becomes the “smallest.”
Building in linear time
The timing above contained the line heapq.heapify(waiting), which turns a ready-made list into a heap. The obvious way is to add the items one at a time with push: $n$ times $O(\log n)$, $O(n \log n)$ in all. That is how the heap’s inventor built it. There is a faster way, and it works almost the other way around.
Put the items into the array as they are, and you have a complete tree, only without order. The leaves (the second half of the array) are already tiny correct heaps: there is nothing under them. Now go through the other nodes from the end toward the beginning and sift each of them down. When a node’s turn comes, both its subtrees are already heaps, and after the sifting the node’s whole subtree is a heap as well. The root is sifted last, and the heap is ready. This is Robert Floyd’s method. Both methods are compared below on the worst input for the first one: numbers in decreasing order, where every newcomer rises all the way to the root.
One by one: 8, 11, almost 15 comparisons per item, and the number grows with the logarithm. Bottom-up: no more than two per item, however many items there are. A short count explains why: most of the work falls to the nodes that don’t have far to sink.
Sifting down every node, from the last parent back to the root, turns an array of $n$ items into a heap in $O(n)$ comparisons: fewer than $2n$.
Say a node has $j$ levels beneath it: a leaf has $j = 0$, its parent $j = 1$, and so on. When sifted, such a node sinks at most $j$ levels and spends two comparisons on each, one per child. The number of nodes with a given $j$ in a complete tree is about $n / 2^{j+1}$: half the nodes are leaves, a quarter are their parents, an eighth are the next ones up. Summing over all $j$:
$$\sum_{j \ge 1} \frac{n}{2^{j+1}} \cdot 2j \;=\; n \sum_{j \ge 1} \frac{j}{2^j} \;=\; n \left(\frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \ldots\right).$$Call the sum in parentheses $S$. Then $S - S/2 = \frac12 + \frac14 + \frac18 + \ldots = 1$: from every term $\frac{j}{2^j}$ we have subtracted $\frac{j-1}{2^j}$, leaving plain powers of two. So $S = 2$, and there are about $2n$ comparisons. A careful count with the rounding gives the same bound: on any input there are fewer than $2n$. The run above counted 1,982 for a thousand items and 199,978 for a hundred thousand.
The two methods have opposite arithmetic. When items are added one by one, the most numerous ones, those that came last and sit at the bottom, have the longest way to go, all the way up to the root. In Floyd’s method only the root and its nearest descendants travel far, and half the nodes, the leaves, don’t move at all. The heap widget above has both buttons: build the same heap both ways and compare the counters.
Heapsort
A sort made from a heap suggests itself: build a heap and take out the smallest $n$ times. That is $O(n)$ for building and $n$ times $O(\log n)$ for the extractions, $O(n \log n)$ in all, the same as merge sort, and in the worst case too. Floyd’s improvement was to do without a second list. After each extraction the heap is one cell shorter, and the cell freed at the end of the array is the right place for the answer. For the answer to pile up in increasing order at the end, the heap is turned upside down, with the largest on top. The code is the same, with the comparison reversed.
Under the cell is the array at every step of the second phase: the green tail is the finished answer, and to the left of the pointer is the heap, a cell shorter at every step. Heapsort runs in $O(n \log n)$ always, on any input, and needs no extra memory beyond a couple of variables. Quicksort from Chapter 21 has a quadratic worst case, and merge sort needs a second array of the same length. But the heap has drawbacks of its own. It jumps around memory, from the root to distant leaves, and processors dislike that (Chapter 34 explains why). And it is unstable: equal items can trade places.
That is why libraries keep heapsort as insurance. The std::sort of many C++ implementations is introsort: a quicksort that watches the depth of its recursion and, if the depth grows suspiciously, switches to heapsort. The worst case of quicksort becomes impossible, while in ordinary cases quicksort does the work.
The ten strongest from a stream
In Chapter 6 we found the ten strongest earthquakes in the catalog: we sorted all 19,073 quakes and took the first ten. And the task “Top k” promised a faster way, which rests on a heap. Suppose the quakes come as a stream, one after another, in the order they happened from 2015 on. We keep a heap of the $k$ best so far, a heap with the smallest on top. Then the root holds the weakest of the best: the bar to clear. Each new quake is compared with the root. Weaker than the bar, it passes by after one comparison. Stronger, it pushes the root out and takes its place in the heap, $O(\log k)$.
The catalog has 19,073 quakes, arriving in order of time. How many times do you think the board of the ten strongest will change, counting the first ten that fill the empty board?
84 times; check it below. If the quakes came in random order, the board would change on average about $k\,(1 + \ln (n/k))$ times, which for $k = 10$ and $n = 19\,073$ is about 85. A new record among many is a rarity, and it gets rarer as the stream goes on.
heapreplace does two jobs in a single sifting: it takes out the root and puts in the new item. The time is $O(n \log k)$ instead of the $O(n \log n)$ of sorting. The gain in memory is worth even more: the heap needs $k$ cells, and there is no need to hold the whole catalog. So the stream can be endless, like a generator from Chapter 10, or too big for memory, like a year of a server’s request log or every bid on a stock exchange.
If the stream comes in increasing order, the bar creeps up with it, and the board changes all the time. If all the magnitudes were different, every new quake would push out the root: that is the worst case, $n \log k$ comparisons. Our magnitudes are almost all rounded to tenths, and a quake equal to the bar doesn’t get in, so at $k = 10$ there are 427 changes, five times as many as in time order but far from 19,073. If the stream comes in decreasing order, the board fills with the first $k$ quakes and never changes again. Live data usually behaves like a shuffled stream: the bar shoots up early, and after that almost everything passes by after one comparison.
heapq has all this ready-made: heapq.nlargest(10, quakes, key=lambda q: q[4]) and heapq.nsmallest work this way. The module also has heapq.merge, which merges several sorted streams into one: a heap holds one item from each stream, its current one, and the smallest of them is the next in the answer. One of the chapter’s tasks is built on this idea.
The event calendar
One last look inside the emergency room from the start of the chapter: how does the program know what happens next? The island of rabbits and foxes from Chapter 12 lived by ticks: every day every animal made a move. Simulating an emergency room that way would be wasteful. A patient comes every few minutes, treatment takes half an hour, and in most minutes nothing happens at all. So the program jumps from event to event.
There are two kinds of events here: “a patient arrived” and “a doctor is free.” Each is a pair (time, what happened), and all future events lie in a heap ordered by time. The program takes out the nearest one, moves the clock to its time and handles it, and in doing so it may put new events into the heap: a patient has been called, so in so many minutes a doctor will be free. This is event-driven simulation, and it runs on two priority queues: the event calendar, by time, and the corridor, by urgency. The whole emergency room fits in about fifty lines; below, it runs the same day with three different dispatchers.
Six patients an hour for two doctors make a busy but manageable day. Under “first come” everyone waits about the same, around a quarter of an hour, and the reds too. Under “by severity” the reds and oranges wait two or three minutes, while the blues wait half an hour on average and almost three hours at the longest. Larrey would have approved.
Eight an hour is more than two doctors can see, and the corridor fills up all day. Under “by severity” a blue patient now waits eight hours on average, and the unluckiest one fifteen and a half. As long as urgent patients keep coming, a non-urgent one is never called. This is called starvation, and it lies in wait for any priority queue under load.
The third rule, “by deadline,” cures starvation with a single line. Its key is the moment the waiting limit runs out: the arrival time plus 0, 10, 60, 120 or 240 minutes. A red patient who arrives now is still ahead of almost everyone. But a blue patient who has waited four hours overtakes a yellow one who has only come in: the blue one’s limit ran out earlier. Nobody waits forever anymore. The urgent cases pay for it: at eight patients an hour the reds now wait 10 minutes instead of 6. And the key doesn’t change over time, because each patient’s deadline is known on arrival. The heap never has to recompute anything, even though in effect a patient’s priority grows with waiting.
A computer solves the same problem without pause. An operating system’s scheduler picks which of hundreds of programs gets the processor for the next millisecond, and it too must not starve the background tasks; we will build one in Chapter 37. The language Simula from Chapter 12 had an event calendar built in from the start: there it is called the sequencing set, and its events stand in increasing order of time. And the heap will come back to the course twice more: in Chapter 23 it will glue Huffman codes together from the two rarest letters, and in Chapter 24 it will tell a navigation app which intersection is closest.
Tasks
Four tasks for the chapter’s four techniques: a priority queue of your own, the top k, merging streams, and two heaps at once. The tests check the edges (empty inputs, repeats, ties) and large inputs with a time limit.
Write a class PriorityQueue, a priority queue on a heap of your own, without the heapq and bisect modules and without sorting:
push(item, priority)adds an item with a priority (a number; smaller means more urgent);pop()takes out and returns the item with the smallest priority, and among equals the one added earlier;peek()returns the same item without taking it out;len(q)tells how many items are in the queue.
pop and peek on an empty queue raise IndexError. Items can be anything, including dictionaries, which can’t be compared. Two hundred thousand operations must fit into four seconds.
The starter is the “first attempt” from the chapter, and it has two problems. Find both: what happens with equal priorities when the items are dictionaries? And what does pop cost?
Keep triples (priority, insertion number, item) in the heap. The number is a counter that grows with every push: it makes the keys unique, so the comparison never gets as far as the items themselves, and equal priorities come out in the order they went in.
Sift up and down as in the cells “push.py” and “pop.py” above. Don’t forget the case of a heap with one item: after pop() takes the last one, there is nobody to move into the root.
Comparing the slices a[i][:2], the pairs (priority, number), makes it plain that the item takes no part in the comparison at all. Comparing whole triples works too: the numbers are unique, so the tuple comparison is settled at the second element. That is what the heapq documentation recommends.
Write k_smallest(stream, k): return a list of the k smallest numbers of a stream in increasing order (all of them if there are fewer than k). The stream is any iterable, including a generator that can be gone through only once; in the tests it holds up to two million numbers. You may not use sorted, .sort(), heapq.nsmallest or heapq.nlargest: solve it with the heap from the chapter. heappush, heappop and heapreplace are allowed.
This is the board from the earthquake section, turned around: we keep the $k$ smallest, and the bar is the largest of them. That calls for a heap with the largest on top. heapq has none, so push the numbers with a minus sign.
A new number gets in only if it is smaller than the bar: x < -heap[0]. Then heapq.heapreplace(heap, -x).
At the end the heap holds the answer, but not in order. heappop hands out the smallest of the negated numbers, which is the largest of yours: collect them all and reverse the list. Check the case k = 0 separately.
The time is $O(n \log k)$, the memory $O(k)$, and the stream is read once. For two million numbers and $k = 10$ almost every number is turned away by a single comparison with the bar.
A server has a thousand logs, each already sorted by time. Write merge_sorted(lists), which takes a list of lists, each sorted in increasing order, and returns one combined sorted list. The lists may be empty and of different lengths, and numbers repeat. You may not use sorted, .sort() or heapq.merge. The tests have two thousand lists, four hundred thousand numbers in all: comparing the heads of all the lists at every step won’t be fast enough.
The starter is correct, but at every step it looks at all $k$ heads: $O(N \cdot k)$. Keep the heads in a heap, and the smallest of them is found in $O(\log k)$.
Push triples (value, list number, position in the list) onto the heap. When you pop a triple, the value goes into the answer, and the next item of the same list, if there is one, goes onto the heap.
Each of the $N$ numbers enters the heap once and leaves it once: $O(N \log k)$. The list number in the triple tells you where to take the next item from when values are equal, and it keeps the comparison from reaching anything that can’t be compared. This is how sorted chunks of data too big for memory are merged: each chunk is sorted on its own, and then a heap merges them. Replacing the heappop and heappush with a single heapreplace makes it a little faster still.
A sensor sends numbers one after another, and after each one you need to know the median of everything sent so far. Write running_median(numbers), which returns a list of medians: element $i$ is the median of the first $i + 1$ numbers. For an odd count the median is the middle element by size; for an even count, the mean of the two middle ones. For example, running_median([5, 15, 1, 3]) → [5, 10.0, 5, 4.0]. The tests have four hundred thousand numbers; sorting after every number or inserting into a sorted list won’t be fast enough.
Split the numbers read so far into two halves, the smaller and the larger. The median sits at the border: the largest of the smaller half and the smallest of the larger one. The smaller half needs a heap with the largest on top (negated numbers), and the larger half an ordinary heap.
Keep two rules: everything in the lower heap is no larger than everything in the upper one, and the lower heap is bigger than the upper one by at most one item. Push a new number onto the lower heap, then move its largest to the upper one, and if the upper heap has become bigger, move its smallest back.
Each number takes at most five heap operations, three heappush and two heappop, each $O(\log n)$, so the whole thing costs $O(n \log n)$, and at any moment the median lies at the root of one of the heaps. Passing every number through the upper heap looks like a detour, but it guarantees the first rule: only a number no larger than everything in the upper heap can land in the lower one.
What next
Everything we have put into structures so far lived on its own: a patient in the corridor, a quake in the catalog, a word in the dictionary. Even in a tree each node has one boss, and between two nodes there is only one path. But data can be connected. Friends know friends of friends, and acquaintances form circles. Subway stations are linked by tracks and transfers, and a hundred routes lead from one to another. The pages of a website link to each other, and the chapters of this textbook to the chapters you need to read first. About such data people stop asking “who is next?” and start asking “how do I get from here to there, and in how many steps?” They say any two people on Earth are linked by six handshakes. In the next chapter we will put that to the test on the Moscow Metro and on this course itself.