Find Median from Data Stream

Problem

Monitoring systems compute running percentiles (p50, p99) over metric streams that arrive continuously. Sorting the whole dataset on each new sample is too slow. The two-heap split maintains O(1) median access by keeping the lower and upper halves in separate heaps. Design a data structure that supports adding integers from a stream and querying the median at any point.

add_num(1) → find_median() = 1.0
add_num(2) → find_median() = 1.5
add_num(3) → find_median() = 2.0
add_num(4) → find_median() = 2.5
add_num(5) → find_median() = 3.0

Solution

Approach: two-heap split - a max-heap for the lower half, a min-heap for the upper half.

The median sits at the boundary between the smaller and larger halves of the data, so keep each half in its own heap with that boundary at the heaps' tops. lower is a max-heap (simulated by negating values, since heapq is a min-heap) holding the smaller values; upper is a min-heap holding the larger ones. add_num always pushes to lower first, then runs two rebalances. The order rebalance: if lower's top now exceeds upper's top (-lower[0] > upper[0]), move that element across, restoring the invariant max(lower) <= min(upper). The size rebalance: if the heaps differ by more than one element, shift one top across so they stay within one of equal size. find_median then reads in O(1) - when lower is larger it holds the lone middle element (-lower[0]); otherwise the count is even and the median is the average of the two tops (-lower[0] + upper[0]) / 2.

Trace 1,2,3: add 1 -> lower=[-1]. Add 2 -> push to lower, rebalance size -> lower=[-1], upper=[2], median 1.5. Add 3 -> push, order rebalance moves 2's competitor so lower=[-2,-1], upper=[3], median 2.

Edge cases: the order rebalance is skipped when upper is empty (the invariant is vacuously true). Negative inputs work, since negating a negative is just its positive image.

Complexity: O(log n) per add_num (a couple of pushes and a pop), O(1) per find_median, O(n) space for all stored values.