Skip to content
Tutorials Center
My learning

Topics

Lesson 109 of 225 ยท Heaps

Running Median and Two Heaps

Find the median of a data stream in O(log n) per number with two heaps in Python. Compare brute force, bisect and the two-heap pattern, plus the sliding window idea.

The median is the middle value of a sorted collection. It is more robust than the average: one billionaire in a room changes the mean income dramatically but barely moves the median. Services use medians for response times, house prices and sensor readings. Often the data arrives one value at a time, and you must report the median after every new number. That is the running median (or median of a data stream) problem.

Sorting after each arrival is wasteful. The elegant solution is the two-heap pattern: split the numbers into a lower half and an upper half, keep the lower half in a max-heap and the upper half in a min-heap, and the median is always at one or both of the tops. It is one of the most reusable heap tricks, and it extends to sliding windows and percentiles. You should know binary heaps and heapq before reading on.

The definition

For n numbers in sorted order:

  • if n is odd, the median is the middle one (position n // 2, 0-based),
  • if n is even, the median is the average of the two middle ones.

For [2, 7, 9] the median is 7. For [2, 7, 9, 12] it is (7 + 9) / 2 = 8.0.

Brute force: sort every time

After each new number, sort everything seen and read the middle.

  • Time: O(n log n) per query, so O(nยฒ log n) for a stream of n numbers.
  • Space: O(n).

A smarter version keeps one list sorted, using bisect.insort to insert each new number in place. Finding the position is O(log n), but shifting the elements to make room is O(n). The median is then O(1), but each insert is O(n), so a stream costs O(nยฒ) overall. That is acceptable for thousands of numbers and painful for millions.

Python Brute force and the sorted-list version

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two-heap idea

The median depends only on the middle of the sorted order. We do not need the two halves to be sorted, just to be separated: everything in the lower half is less than or equal to everything in the upper half.

  • low: a max-heap holding the smaller half. Its top is the largest of the small numbers.
  • high: a min-heap holding the larger half. Its top is the smallest of the large numbers.
TEXT
sorted order:   1  3  5  7  8  9  10  15
                \________/  \__________/
                  low           high
              (max-heap)    (min-heap)
                top = 7      top = 8

n even  -> median = (top of low + top of high) / 2 = (7 + 8) / 2 = 7.5

The two tops are exactly the two middle values. Keep the heaps balanced so that len(low) is equal to len(high) or exactly one larger. Then:

  • if the sizes are equal, the median is the average of both tops,
  • if low has one extra element, the median is the top of low.

Adding a number

  1. Push the new number into low (the max-heap), then move the top of low to high. This guarantees that every number in low is at most every number in high, even if the new number was large.
  2. If high now has more elements than low, move the top of high back into low.

Each step is a constant number of heap operations, each O(log n). Reading the median is O(1).

Since heapq only provides min-heaps, low stores negated numbers.

Python The two-heap running median

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the trace. After adding 5 and then 15, the lower half is [5] and the upper half [15]; the median is their average, 10.0. Adding 1 puts 1 in the lower half (now [1, 5]), making it one larger, so the median is its top, 5.

Why step 1 sends x through both heaps

You might be tempted to compare x with the tops and decide which heap it belongs to. That works, but it needs more cases. Pushing into low and then moving the largest of low to high handles every case uniformly, and it keeps the invariant max(low) <= min(high) without extra comparisons. The cost is one extra heap operation per number, which is still O(log n).

Complexity

Operation Time Notes
add O(log n) a few pushes and pops
median O(1) read one or two tops
space O(n) every number is stored once
Approach add median whole stream of n
sort every time O(1) O(n log n) O(nยฒ log n)
sorted list + insort O(n) O(1) O(nยฒ)
two heaps O(log n) O(1) O(n log n)

Checking the result against a trusted answer

When you write an algorithm like this, compare it with a simple reference on random data, using a seeded random generator so the check is repeatable.

Python Verify against statistics.median

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sliding window median

A related problem: given an array and a window size k, report the median of every window of k consecutive numbers (see sliding window). The window moves one step at a time, so one number leaves and another enters.

Simple approach: keep a sorted list of the current window. Remove the leaving number with bisect_left (O(k) because of shifting), insert the new one with insort (O(k)), read the middle. Total time is O(nยทk) with very small constants, which is plenty for moderate k.

Python Sliding window median with a sorted window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two-heap approach: the same low and high heaps work, with one extra problem: heaps cannot remove an arbitrary number cheaply. The standard fix is lazy deletion (see heapq): when a number leaves the window, do not remove it from the heap. Instead, record it in a "to delete" counter and update the logical sizes of the two halves. Whenever a deleted number reaches the top of a heap, discard it. The balance rule is applied to the logical sizes, so each step stays O(log k) amortized. The total is O(n log k), better than O(nยทk) for large windows. The code needs care, so this lesson shows the idea only.

  • Percentiles: put the p percent smallest numbers in low and the rest in high, and keep that ratio instead of the half-and-half balance.
  • Median of a fixed set: if all the data is in memory and you need only one median, quickselect finds it in O(n) average time.
  • Bounded values (for example, ages 0 to 120): a counting array and a running total find the median in O(range) per query with no heaps at all.
  • Two heaps for other problems: the pattern also solves "maximize capital" scheduling problems, where one heap holds items you can afford and the other holds the rest.

Common mistakes

  • Forgetting to negate for the max-heap. heapq is a min-heap, so low stores -x and you must negate again when you read it.
  • Breaking the order invariant. Every number in low must be at most every number in high. Pushing into the wrong heap without the transfer step violates it.
  • Wrong size rule. The rule is len(low) == len(high) or len(low) == len(high) + 1. If the sizes drift further apart, the tops are not the middle.
  • Integer division. For an even count the median is (a + b) / 2. Use /, not //, unless the problem asks for the floor.
  • Reading the median of an empty stream. Decide what to return before the first number arrives.
  • Mixing up the heap that gets the extra element. If you let high hold the extra, remember to read its top for odd counts.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the two-heap median method, which kind of heap holds the smaller half of the numbers?

    The median needs the largest value of the lower half, so the lower half lives in a max-heap. The upper half lives in a min-heap, whose top is its smallest value.
  2. 2. The stream so far has 7 numbers and low holds 4 of them. What is the median?

    With an odd count, low holds the extra element. The median is the largest of the lower half, which is the top of low.
  3. 3. What is the cost of adding one number to the two-heap structure and then reading the median?

    Adding does a constant number of heap pushes and pops, each O(log n). Reading the median only looks at one or two tops, which is O(1).
  4. 4. Why is a sorted list with bisect.insort O(n) per insertion, even though the position is found in O(log n)?

    Lists are arrays. Finding where to insert is a binary search, but inserting in the middle moves every later element one slot, which costs O(n).
  5. 5. For an even number of values, the running median is...

    By definition the median of an even-sized collection is the mean of the two middle values, which are the tops of the two heaps.

Summary

  • The running median reports the median after each new value of a stream. Sorting every time costs O(n log n) per query, and a sorted list costs O(n) per insert.
  • The two-heap pattern keeps the lower half in a max-heap and the upper half in a min-heap, with the max-heap equal in size or one larger.
  • Add by pushing into low, moving its top to high, and rebalancing. This is O(log n). The median is read from the tops in O(1).
  • Python needs negated values for the max-heap.
  • A sliding window median can use a sorted window (O(nยทk)) or two heaps with lazy deletion (O(n log k)).
  • Always compare a new implementation with a simple reference on seeded random data.

Next: Merging K Sorted Lists