Find Median from Data Stream

The idea

I need the median after every insert, on a stream that never stops growing. Sorting on each query is too slow. But the median only ever cares about the two middle elements. So I keep the data split into a low half and a high half, and I only ever look at the boundary between them.

A max-heap holds the low half, so its top is the largest small number. A min-heap holds the high half, so its top is the smallest large number. Those two tops are exactly the elements the median is made of.

Brute force, then the cut

The brute-force version stores everything in a list and sorts on each findMedian call. That's O(n log n) per query. Even keeping a sorted list costs O(n) per insert from shifting elements.

The cut is realizing I never need the whole order, just the middle. Two heaps give me O(log n) inserts and O(1) median reads. The only real work is keeping them balanced: every new number goes into one heap, then I rebalance so the sizes differ by at most one. Python only has a min-heap, so I negate values to fake a max-heap.

import heapq
 
 
class MedianFinder:
    def __init__(self) -> None:
        self.low: list[int] = []   # max-heap (negated), the smaller half
        self.high: list[int] = []  # min-heap, the larger half
 
    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)
        # move the biggest of low into high to keep ordering correct
        heapq.heappush(self.high, -heapq.heappop(self.low))
        # rebalance so low is never smaller than high
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
 
    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

Why it holds

Every insert funnels through low first, so the largest low value always lands where it belongs relative to high. The rebalance keeps len(low) >= len(high) and the gap at most one. When the total is odd, low has the extra element and its top is the median. When it's even, the median averages the two tops. Each call does a constant number of heap operations, so inserts are O(log n) and reads are O(1).