Running median with two heaps

Why this matters

The median is the middle value of a list when the values are put in order. It is a better "typical value" than the average when a few extreme values would pull the average far away. A website that tracks the median response time of its servers can see that most users are fast even when one request took ten seconds. A teacher who wants to know a typical test score looks at the median for the same reason.

Now picture the median of a stream. Values arrive one at a time, and after each one you must report the median of everything seen so far. You could sort the whole list again after every value, but that costs O(n log n) each time, which is too slow for a long stream. You could keep the list sorted by inserting each value in its place, but inserting into the middle of an array costs O(n) per value. Neither method is good enough when the stream is very long.

This lesson solves the problem with two heaps. A max-heap holds the smaller half of the values, and a min-heap holds the larger half. The median then lives at the boundary between the two halves, and both halves are accessible at their roots. Each new value costs O(log n) to add. This is the last technique in the module, and it draws on everything you have learned: the heap shape, push and pop, the two kinds of heap, and the root as the place to read the answer.

The lesson ends with a short recap of the whole module, so you can check your understanding before you attempt the module assignment.

The idea from first principles

Start with a list of values in order. Suppose there are seven values, sorted: 1, 3, 5, 7, 8, 9, 15. The median is the middle one, 7, because three values are below it and three are above it. If there were an even number of values, such as 1, 3, 5, 7, the middle is between 3 and 5, so the median is (3 + 5) / 2 = 4.

Notice what the median really depends on. It depends on the largest value of the lower half and the smallest value of the upper half. For seven values, the lower half is 1, 3, 5 and its largest is 5. The upper half is 8, 9, 15 and its smallest is 8. For an odd count, the median is the top of the half that has one extra value. For an even count, it is the average of the two tops.

So if we could keep the lower half in a structure where we can read its largest value fast, and the upper half in a structure where we can read its smallest value fast, we would have the median at all times. Those two structures are exactly a max-heap and a min-heap.

An everyday picture

Imagine lining up people by height, shortest on the left and tallest on the right. The median is the person in the middle. Now imagine the people arrive one at a time. You do not want to re-line everyone each time. Instead, you keep two lines. The left line holds the shorter half, with the tallest person of that half standing at the front, nearest the middle. The right line holds the taller half, with the shortest person of that half at the front, nearest the middle too.

When a new person arrives, you decide which line they belong to by comparing with the front of the left line. Then you rebalance if one line has become two or more people longer than the other. The median is always at the two fronts: if the left line is one longer, the median is the front of the left line. If the lines are equal, the median is the average of the two fronts.

The two fronts are the roots of the heaps. The left line is a max-heap, because its root is the largest value in the lower half. The right line is a min-heap, because its root is the smallest value in the upper half.

The two invariants

An invariant is a rule that must always be true after each step of the program. Two invariants keep this method correct.

The first invariant is about values. Every value in the lower half is less than or equal to every value in the upper half. This means the top of the lower heap is always at most the top of the upper heap. It is what makes the median sit at the boundary.

The second invariant is about sizes. The lower half holds either the same number of values as the upper half, or one more. So the number of values in the lower heap is size of upper heap or size of upper heap + 1. This keeps the median at a fixed place: after an odd count, the lower heap has the extra value, and its top is the median.

Every operation in the method must keep both invariants true. The insert rule and the rebalance rule do exactly that.

Two rows: a max-heap holding the lower half and a min-heap holding the upper half, with the median at the boundary

Inserting a new value

When a new value x arrives, do two things.

First, decide the half. If the lower heap is empty, or if x is at most the top of the lower heap, push x into the lower heap. Otherwise push x into the upper heap. The comparison with the lower top is what keeps the first invariant: x goes to the half where its value belongs.

Second, rebalance. After the push, the sizes may break the second invariant. If the lower heap now has two or more values more than the upper heap, move the top of the lower heap to the upper heap. If the upper heap now has more values than the lower heap, move the top of the upper heap to the lower heap. Each move takes one pop and one push, so the rebalance costs O(log n).

Moving a value between heaps keeps the first invariant because the value that moves is always at the boundary: the largest of the lower half moves to the upper half, where it is still the smallest-possible value of that side, and the same holds in the other direction.

Reading the median

The median is read from the roots, without changing either heap.

• If the lower heap has more values than the upper heap, the count is odd, and the median is the top of the lower heap.
• Otherwise the counts are equal, the count is even, and the median is (top of lower + top of upper) / 2.

An even median can be a fraction, such as 4.5, so the program must handle the .5. A clean way is to compute twice the median, which is always a whole number. For odd counts, twice the median is 2 * lower top. For even counts, it is lower top + upper top. Then print the value divided by two, with .5 added when the doubled value is odd. The program below does exactly that.

A trace on a small stream

Let us follow the rule on seven values, 5, 15, 1, 3, 8, 7, 9. We write the lower heap low (largest on top), the upper heap high (smallest on top), and the median after each step.

Check the last row. After adding 9, the upper heap has four values and the lower heap has three. The rebalance moves 7 from the top of the upper heap to the lower heap. Now the lower heap holds 7, 5, 3, 1 and the upper heap holds 8, 9, 15. The count is seven, which is odd, so the median is the top of the lower heap, 7. Sorting the seven values, 1, 3, 5, 7, 8, 9, 15, gives the middle value 7. The method agrees.

Why two heaps, and not another design

Three other designs come to mind first. A sorted array gives the median in O(1) by index, and it is easy to read. But each insert shifts about half of the values, which costs O(n) per insert. A balanced search tree, such as a set, can walk to the middle in O(log n), but finding the middle needs extra bookkeeping, and the code is longer and harder to check. A single heap cannot give the median at all, because it gives only one end. Two heaps split the work cleanly. Each heap gives its boundary value in O(1), each insert costs O(log n), and no walking is needed.

Walking through an even count

Take the values 2, 8, 6, 4. The sorted list is 2, 4, 6, 8, so the median is (4 + 6) / 2 = 5. Now follow the two heaps.

1. Add 2. It goes to the lower heap, which is empty. The lower heap is {2}, and the median is 2.
2. Add 8. It is not at most 2, so it goes to the upper heap: {8}. The sizes are equal, so there is no move. The median is (2 + 8) / 2 = 5.
3. Add 6. It is not at most the lower top 2, so it goes to the upper heap: {6, 8}. The upper heap is now bigger, so its smallest value, 6, moves to the lower heap. The lower heap is {6, 2} and the upper heap is {8}. The median is the lower top, 6.
4. Add 4. It is at most the lower top 6, so it goes to the lower heap: {6, 4, 2}. The lower heap is now two bigger than the upper heap, so its largest value, 6, moves up to the upper heap. The lower heap is {4, 2} and the upper heap is {6, 8}. The sizes are equal, so the median is (4 + 6) / 2 = 5.

The final answer is 5, which matches the sorted list. Step 3 shows the purpose of the rebalance. The value 6 was bigger than the lower top, so it went to the upper heap, but that made the upper heap too big. Moving its smallest value across shifted the boundary, and the boundary is exactly where the median is read.

Real-world uses of a running median

A latency dashboard tracks the median response time of a web service, because a few very slow requests would pull an average far away from what most users see. A trading system tracks a running median of prices over a window. A sensor network keeps the median reading from a noisy sensor, which filters out a single bad spike. In each case the values keep arriving, the answer is needed after every value, and the cost of re-sorting would be too high. The two-heap method gives each answer in O(1) and each update in O(log n), which is why it appears in production monitoring code.

Program one: the median after every value

The class below does the work. It holds the two heaps as members, so they persist between calls. The method add inserts a value and rebalances. The method twiceMedian returns twice the current median, as described above. The main function reads a count and then the values, and prints the median after each one. The formatting function turns the doubled value back into a readable number.

Type this into the Input box:

7
5 15 1 3 8 7 9

The output is:

5
10
5
4
5
6
7

Each line matches the trace table. The median after two values is 10, which is the average of 5 and 15, and the program prints it as 10, because twiceMedian is 20 and 20 / 2 is 10. The even median 4 after four values comes from (3 + 5) / 2.

Notice that twiceMedian is const and only reads the roots. It does not change either heap. That is the reason the method is cheap, and it is a good habit: a read should never move data.

Program two: watching the heaps

The best way to trust this method is to see the two heaps change. This program prints each heap after every value. The copies in show keep the originals safe, because to print a heap in order you must pop it, and popping destroys it. Each copy is popped and the values are printed from the top.

Type this into the Input box:

6
4 9 2 7 1 8

The output is:

added 4, median 4
  low (largest first): 4
  high (smallest first):
added 9, median 6.5  
  low (largest first): 4
  high (smallest first): 9
added 2, median 4
  low (largest first): 4 2
  high (smallest first): 9
added 7, median 5.5
  low (largest first): 4 2
  high (smallest first): 7 9
added 1, median 4
  low (largest first): 4 2 1
  high (smallest first): 7 9
added 8, median 5.5
  low (largest first): 4 2 1
  high (smallest first): 7 8 9

Read the first step. The first value 4 goes to the lower heap, and the median is 4. The second value 9 is larger than 4, so it goes to the upper heap. The two halves have one value each, so the median is (4 + 9) / 2 = 6.5. The doubled median is 13, an odd number, so the formatting function prints 6.5.

The trace shows the most important detail of the method: each step adds one value to a half, then moves one value across if needed, so the two invariants are kept.

Why each insert costs O(log n)

Reading the median is O(1), because it only reads two roots. Adding a value is one push, which costs O(log n) on one of the heaps, and at most one move, which is one pop plus one push, also O(log n). So each add costs O(log n), and the total for a stream of n values is O(n log n).

Compare this with the other options. Sorting the whole list after every value costs O(n log n) per value, which is O(n squared log n) in total. Inserting each value into a sorted array costs O(n) per value, which is O(n squared) in total. The two-heap method is far faster when n is large, and its memory is O(n), because every value is stored in exactly one heap.

Program three: check the method against brute force

When a method is clever, test it against a dumb version that you trust. The brute-force version keeps every value in a list and, for each step, sorts a copy and reads the middle. It is slow, but it is simple enough to be obviously correct. This program runs 200 rounds with random values, and for each value it compares the two methods.

The random numbers come from the same small generator as in the last lesson. The values are between 0 and 99, which keeps the code simple, since every median is then nonnegative.

The output is:

comparisons: 3987
mismatches: 0

Zero mismatches over more than four thousand steps is strong evidence that the method is right. A bug in the rebalance, such as forgetting to move a value, would show up as a mismatch within a few rounds. This is the same test habit as the last lesson, and it is worth using every time you write a data structure.

Program four: a long stream

A long stream shows the cost of the method in practice. The next program adds 100000 values from the generator, and it keeps a running checksum: the sum of every doubled median, reduced modulo a large prime, so the number stays small. The output is a single line of results. The program does not read input.

The output is:

values: 100000
final median: 16423
checksum: 268449216

The program does 100000 insertions, each costing O(log n), so the work is a few million simple steps. On a typical computer it finishes almost instantly. Had you used a sorted array with insertion in the middle, the same job would copy about two and a half billion numbers in total, which takes far longer. The heap method is the reason a live dashboard can keep a median up to date.

Complexity and memory

Compare with sorting. A full sort gives the median in O(n log n) once, but it must be repeated after each value to answer each query, which costs O(n squared log n) overall for a stream. The two-heap method pays O(log n) per value and answers every query in O(1).

What happens inside

Each heap is a vector with the heap rule applied. The lower heap's root is at index 0 of its vector, and so is the upper heap's root. Reading the median means reading one or two numbers from the front of two vectors, which costs almost nothing. A push appends a value at the end of a vector and sifts it up. A pop moves the last value to the root and sifts it down. The moves between heaps are a pop from one and a push into the other, so the values are copied between two vectors, not moved in memory. The memory layout is the same as in the second lesson.

The two heaps never need to know about each other except through the rebalance step. Each heap keeps its own rule. The median rule uses both roots, and the insert rule uses one root to decide the half. This separation is why the method is simple to reason about once you see the invariants.

Common mistakes and the symptoms they cause

Mistake 1: making both heaps the same kind

If both heaps are max-heaps, the upper half's root is its largest value, not its smallest, and the median is wrong from the third value on. The symptom is a median that is too large. Check the declarations: the upper heap must use greater<int>.

Mistake 2: skipping the rebalance

If you insert but never rebalance, the sizes drift apart. The median reads the wrong root, and the answer can be far off. The symptom is a median that looks fine for a few values and then jumps. Run program three; it catches this at once.

Mistake 3: reading a root when the heap is empty

The first value is special. The check low.empty() must come before x <= low.top(), because top on an empty heap is undefined. If you forget the check, the first insert may crash with a segmentation fault, or it may compare with garbage and seem to work for some inputs. Always check empty before reading a root.

Mistake 4: integer division for an even median

If you print (low.top() + high.top()) / 2 directly, the program prints 4 for a median of 4.5. That is a silent error, because the program does not crash. The fix is to work with twice the median, as the program does, and print the .5 yourself.

Mistake 5: the wrong size test

Some programs rebalance when the sizes are equal, which is not needed. The invariant allows the lower heap to be one bigger, and only a difference of two or more needs a move. Moving on a difference of one just makes the next insert move back, which is wasted work and makes the code harder to follow.

Mistake 6: a comparison that sends the value to the wrong half

If the test is x < low.top() instead of x <= low.top(), equal values go to the upper half. That is still correct, because the first invariant only needs the lower half to be at most the upper half. But a test that goes the other way, such as x >= high.top(), can break it. Keep one clear rule and check it on repeated values.

Debugging walkthrough: the median is wrong after some value

Suppose program three reports a mismatch. Here is a method that finds the cause quickly.

1. Print the value that caused the first mismatch, along with the two heaps. Program two's show function does this.
2. Check the first invariant. The top of the lower heap must be at most the top of the upper heap. If it is not, the insert rule sent the value to the wrong half.
3. Check the second invariant. The lower heap must have the same size as the upper heap, or one more. If not, the rebalance is missing or wrong.
4. Compute the median by hand from the sorted list, and compare with the roots. The difference shows which root is wrong.

Most bugs are in the declarations or in the rebalance. The two invariants point to the line to change.

Edge cases you should test

• The first value. The lower heap is empty, so the value must go there. The median is that value.
• Two values, equal. Both go to the same half, or one to each. The median is that value.
• All values equal, such as 5 5 5 5. Every median is 5, and the program must never print 5.5.
• Values in increasing order, such as 1 2 3 4 5. Every new value goes to the upper half, and the rebalance then moves values down. The medians are 1, 1.5, 2, 2.5, 3.
• Values in decreasing order, such as 5 4 3 2 1. Every new value goes to the lower half, which rebalances to the upper half. The medians are 5, 4.5, 4, 3.5, 3.
• A very large stream. The method stays fast because each insert is O(log n).

Notice that the program in this lesson only handles nonnegative values. With negative values, the formula twice / 2 rounds toward zero in C++, so -3 and -2.5 would both print as nearby values in the wrong way. A real program must handle the sign carefully, for example by using floor division.

Variations you may meet

Sometimes the stream allows values to leave as well as arrive, such as a sliding window that keeps only the last k values. Then the method needs to delete a value from the middle of a heap, which a heap cannot do directly. A common fix is lazy deletion: keep a second count of values that are waiting to be removed, and skip them when they reach a root. You will meet that technique in the module assignment.

Another variation is a median with a required rounding rule, such as always rounding down. Then the output is just the lower root, or the floor of the average. The two-heap structure does not change.

Interview questions you should be ready for

How do you find the median of a stream? Use two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep the sizes equal or one apart, and read the median from the roots. Each insert costs O(log n), and the median costs O(1).

Why two heaps and not one? A heap gives only one end cheaply. The median needs the largest value of the lower half and the smallest value of the upper half, so it needs both ends. Two heaps provide both.

What is the cost of the naive approach? Sorting after each value costs O(n log n) per value, which is O(n squared log n) for a stream. Inserting into a sorted array costs O(n) per value.

What is the memory? O(n). Every value is stored once, in one of the two heaps.

What changes if the values can also be removed? You need lazy deletion or a balanced tree, because a heap cannot remove an arbitrary value efficiently.

What if the values are already sorted when they arrive? The method still costs O(log n) per value. Each value goes to the upper half, and a rebalance moves the smallest one down, so the work does not change.

Practice

1. Find the median of 2, 9, 4, first by sorting and then with the two-heap method. Write the heaps after each step.

2. For the stream 1, 2, 3, 4, print the median after each value. Show every value that goes to a half.

3. Change the program so the median is always the top of the lower heap, which rounds an even median down. What is the output for 1, 2, 3, 4?

4. Write a short argument for why the rebalance step must move the top of the lower heap, not a random value, to keep the first invariant.

5. The program stores int values. Explain why the doubled median avoids overflow for values up to one million, and why it would matter near the limit of int.

6. Explain in two sentences why reading the median does not change the heaps, and why that matters.

7. Write the brute-force check so it compares the medians as formatted strings instead of doubled integers. Which function must you write, and where does the .5 come from?

8. A stream has n values and the program asks for the median after every value. Give the total cost in terms of n, and compare it with a sorted array that is rebuilt after every value.

9. What would happen if the program had a bug where the upper heap's comparison used less<int> instead of greater<int>? Predict the medians for 1, 2, 3 and then check with the program.

10. Why does the two-heap method need the value of x compared to the top of the lower heap, and not to the top of the upper heap, when deciding where x goes?

11. Modify the long-stream program so it prints the median at every thousandth value instead of only the last one. How many lines do you expect?

12. Explain in plain words what lazy deletion would do for a sliding window median, and why a heap alone cannot delete a value in the middle.

Recap of the module

This module built one data structure, the heap, and then used it in four ways. Here is what you now know, from the first lesson to this one.

• A heap is a complete binary tree with the heap-order rule. It is stored in a vector with the parent of index i at (i - 1) / 2, and its children at 2 * i + 1 and 2 * i + 2.
• Push appends a value and sifts it up. Pop moves the last value to the root and sifts it down, always toward the smaller child in a min-heap. Both cost O(log n). Heapify builds a heap from an array in O(n).
• priority_queue is the standard heap. The default is a max-heap, greater gives a min-heap, and a struct with a comparison gives any order you need. pop returns nothing, and top on an empty queue is undefined.
• Heap sort sorts in O(n log n). The in-place version uses O(1) extra space, but it is not stable.
• The top K pattern keeps a size-limited min-heap for the largest values, and a size-limited max-heap for the smallest. Merging K sorted lists keeps one entry per list in a min-heap.
• The running median keeps two heaps, a max-heap for the lower half and a min-heap for the upper half, with two invariants about values and sizes. Each insert costs O(log n) and each median read costs O(1).
• Test every structure against a slow, obviously correct version, and check the invariants while you debug.

The module assignment that follows combines these ideas in one larger program.