Median after each new reading

Heaps and priority queues Senior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
import heapq
low: list[int] = []   # negated: max-heap
high: list[int] = []
out = []
for r in [5, 2, 8, 1]:
    heapq.heappush(low, -r)
    heapq.heappush(high, -heapq.heappop(low))
    if len(high) > len(low):
        heapq.heappush(low, -heapq.heappop(high))
    if len(low) > len(high):
        out.append(float(-low[0]))
    else:
        out.append((-low[0] + high[0]) / 2)
print(out)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [5.0, 3.5, 5.0, 3.5]

Right: medians of [5], [2, 5], [2, 5, 8] and [1, 2, 5, 8].

Passing every value through the low heap first keeps all of low no bigger than all of high, so the tops are always the middle values.

Why not the others?
  • B [5.0, 3.5, 5.0, 5.0]. With four readings the median is the mean of 2 and 5.
  • C [5.0, 2.0, 5.0, 2.0]. Even counts average the two middle values.

30-second answer

Keep the smaller half in a max-heap and the larger half in a min-heap, with sizes equal or the low half one bigger. Each new value goes to the right half, then one value moves across if the sizes drift. The median is the low top, or the mean of both tops. O(log n) per reading, O(n log n) in total, and O(n) space for the heaps.

Practise saying it · 60 s. No recording, just a timer

Explain the two-heap running median.

Say your answer out loud, then check which of these points you covered:

  • Low max-heap, high min-heap
  • Rebalance sizes
  • O(log n) per reading

Deep dive

The two-heap template answers 'median of a stream' and its sliding-window cousin.

Push to the low heap, move its largest to the high heap, then rebalance; this keeps the order rule without extra checks.

Sorting after every reading is O(n log n) each time.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from heapq import heappop, heappush


def running_median(readings: list[int]) -> list[float]:
    low: list[int] = []  # smaller half, negated
    high: list[int] = []  # larger half
    out: list[float] = []
    for r in readings:
        heappush(low, -r)
        heappush(high, -heappop(low))  # largest of low moves up
        if len(high) > len(low):
            heappush(low, -heappop(high))
        if len(low) > len(high):
            out.append(float(-low[0]))
        else:
            out.append((high[0] - low[0]) / 2)
    return out

Common mistakes

  • Letting the halves differ in size by more than one.
  • Forgetting to negate values in the max-heap.

Senior take & follow-ups

Say the invariant (sizes and order between halves) before coding.

Follow-up questions

Think of your answer first, then open the hint.

  1. What about a sliding window median?

    Show hint

    Same two heaps plus lazy deletion of values that leave the window.

  2. What if values are small integers?

    Show hint

    A count array with a running pointer gives O(range) or better per step.

Similar on Backend: Why percentiles, not averages The Backend page explains p50 and p99 latency for a service; this page keeps the running median of a stream with two heaps.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.