Median from a Data Stream

Numbers arrive one after another and, at any moment, you want the median — the middle value if you sorted everything seen so far. The lazy solution is to keep a list, sort it on every query, and read the middle: that's $O(n \log n)$ per query and hopeless on a fast stream. The elegant solution keeps the data half-sorted at all times using two heaps, so each new number costs $O(\log n)$ and the median is always sitting right there for $O(1)$ reading.

The two-heap idea

Split the numbers into a lower half and an upper half. Store the lower half in a max-heap (so its largest element — the top of the low half — is instantly available) and the upper half in a min-heap (so its smallest element — the bottom of the high half — is instantly available). Keep the two halves the same size, give or take one. Then the median is either the top of the bigger heap, or the average of the two tops when the halves are equal.

$$\text{median} = \begin{cases} \text{top of the larger heap}, & \text{odd count} \\[4pt] \tfrac{1}{2}\bigl(\text{max-heap top} + \text{min-heap top}\bigr), & \text{even count} \end{cases}$$

In words: the max-heap holds everything below the middle and hands you the largest of those; the min-heap holds everything above and hands you the smallest of those. The median lives exactly at that boundary, so you never look deeper than the two tops.

Worked example: streaming 5, 15, 1, 3

Feed the numbers in and watch the heaps rebalance. lo is the max-heap (lower half), hi is the min-heap (upper half):

Insert	lo (max-heap)	hi (min-heap)	Median
5	{5}	{}	5
15	{5}	{15}	(5+15)/2 = 10
1	{1, 5}	{15}	5
3	{1, 3}	{5, 15}	(3+5)/2 = 4

Each insert: push onto one heap, then, if one side grew too big or a value landed on the wrong side, move a single element across the boundary to rebalance. That's a constant number of heap operations, each $O(\log n)$.

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (store negatives — Python heaps are min-heaps)
        self.hi = []   # min-heap

    def add(self, x):
        heapq.heappush(self.lo, -x)                       # tentatively low
        heapq.heappush(self.hi, -heapq.heappop(self.lo))  # largest low -> high
        if len(self.hi) > len(self.lo):                   # keep lo the bigger side
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

The push-to-lo-then-shift-to-hi dance guarantees the two heaps stay ordered relative to each other and balanced in size, without any explicit comparison of the incoming value — a clean trick worth recognizing.

Where it shows up in quant-dev interviews

This is a top-tier streaming question because desks compute rolling statistics on tick data constantly — a running median or a rolling quantile of trade sizes, spreads, or returns, updated on every message without re-sorting the window. The interviewer's follow-ups usually push toward a sliding window (evict the oldest value as it leaves the window, which needs lazy deletion or an indexed structure) or toward an arbitrary percentile rather than the exact middle. The same two-heap balancing idea underpins order-statistic queries generally (Order Statistics) and connects to quantile estimation on streams (Quantile Regression).

If you can explain why the two tops bracket the median, keep the sizes balanced, and handle the max-heap-via-negation detail, you've got one of the most reusable streaming patterns there is — a close cousin of the $O(1)$-access thinking behind an LRU Cache Design.