Maintain an exact streaming median

Appending then sorting n observations costs O(n log n) for one snapshot. Maintaining a sorted list makes median lookup cheap but insertion O(n) because values shift. Two heaps avoid maintaining the full order inside either half; only their boundary values matter for median selection.

Insert into lower if it is empty or the observation is no greater than lower's maximum; otherwise insert into upper. If lower exceeds upper by more than one, move lower's maximum to upper. If upper becomes larger, move its minimum to lower. For odd totals return lower's maximum; for even totals average both roots exactly.

every lower value is ≤ every upper value, and lower has either the same size as upper or exactly one extra. Insertion chooses a valid side relative to the dividing value. Moving the appropriate extreme during rebalancing preserves cross-half order. Thus the roots are exactly the middle one/two order statistics.

Each arrival performs O(log(n+1)) heap work; a query reads O(1) roots. State is O(n) values and O(1) per-operation working slots, excluding growing heap storage. These are word-model costs. Large integer comparisons, negation, and Fraction construction also depend on operand bit length; exactness is preserved rather than treating conversion to float as a harmless presentation step.

Follow-up 1 — delete expired observations. Predict the median after deleting 1 from the example: remaining [2,5,9] has median 5. A heap cannot directly remove an arbitrary buried entry cheaply. Use indexed heaps, an ordered multiset, or lazy deletion with unique identities, logical size counts, root pruning, and compaction.

Follow-up 2 — merge summaries from several machines. Averaging local medians does not produce the global median: partition sizes and value distributions matter. For exact arbitrary values, retain enough order information or exchange selection queries over distributed data. For bounded memory, choose an approximate quantile summary and define its error guarantee; the two heaps are not a compact mergeable summary just because querying them is constant-time.

Senior depth proves both invariants and checks every prefix against sorting. Lead depth distinguishes exact, approximate, windowed, and distributed contracts before committing to storage and communication budgets.

Reference: solution.py (download file, source below); tests verify all cross-half values, sizes, seeded prefix medians, empty behavior, and integers too large for floats.

"""Exact median of all inserted integers using two balanced heaps."""
from fractions import Fraction
import heapq


class StreamingMedian:
    def __init__(self):
        self.lower_half, self.upper_half = [], []

    def add(self, value):
        if not isinstance(value, int):
            raise ValueError("integer observations required")
        if not self.lower_half or value <= -self.lower_half[0]:
            heapq.heappush(self.lower_half, -value)
        else:
            heapq.heappush(self.upper_half, value)
        if len(self.lower_half) > len(self.upper_half) + 1:
            heapq.heappush(self.upper_half, -heapq.heappop(self.lower_half))
        elif len(self.upper_half) > len(self.lower_half):
            heapq.heappush(self.lower_half, -heapq.heappop(self.upper_half))

    def median(self):
        if not self.lower_half:
            raise ValueError("median of empty stream")
        if len(self.lower_half) > len(self.upper_half):
            return Fraction(-self.lower_half[0])
        return Fraction(-self.lower_half[0] + self.upper_half[0], 2)

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/41-streaming-median -p 'test_*.py'