Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python running median: two heaps with an exact even-count result

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A running median partitions seen values between a max-heap of lower values and a min-heap of upper values.

Download Python source kit

Operation contract

The lower heap stores negated integers and may hold one extra value. Every insertion restores order and heap-size balance. Odd prefixes report the lower top; even prefixes return a Fraction of the two tops, so a half-unit result is exact rather than silently converted to a binary float.

Failure and ownership boundary

This is an insertion-only stream; deleting old samples requires delayed deletion or a different structure. The wrapper caps input count and value magnitude. Python heapq top-k: define ties before ranking frequencies, Python quantiles: choose an interpolation policy before reporting a threshold and Python Fraction: exact ratios require an exact input representation cover related choices.

Working program

python
from fractions import Fraction
from heapq import heappush, heappop

def running_medians(values):
    if type(values) is not list or len(values) > 100 or any(type(value) is not int or abs(value) > 10000 for value in values):
        raise ValueError("bounded samples")
    lower, upper, result = [], [], []
    for value in values:
        if not lower or value <= -lower[0]:
            heappush(lower, -value)
        else:
            heappush(upper, value)
        if len(lower) > len(upper) + 1:
            heappush(upper, -heappop(lower))
        elif len(upper) > len(lower):
            heappush(lower, -heappop(upper))
        result.append(Fraction(-lower[0]) if len(lower) > len(upper)
                      else Fraction(-lower[0] + upper[0], 2))
    return result

print([str(value) for value in running_medians([7, 2, 9, 4])])
try:
    running_medians([True])
except ValueError:
    print("boolean rejected")

Output

Output
['7', '9/2', '7', '11/2']
boolean rejected

Costs and limits

Each insertion costs O(log n) and both heaps retain O(n) values; returning each median also retains O(n) fractions. This does not provide a constant-memory sliding median.

Common Mistakes

  • Rebalance both size and ordering.
  • An average of two integer values can be fractional.

Connected lessons

Python heapq top-k: define ties before ranking frequencies, Python quantiles: choose an interpolation policy before reporting a threshold, Python Fraction: exact ratios require an exact input representation.

python
running-median-heaps
Storage details