Lower values are no larger. The median is the boundary between a lower max-heap and upper min-heap.

Think of two bowls touching at their rims. The left bowl reveals its largest value; the right reveals its smallest. Rebalance so the middle always sits at those rims.

What the function promises: MedianFinder accepts numeric values. median raises ValueError before any insertion and returns a float.

from heapq import heappush, heappop

class MedianFinder:
    def __init__(self):
        self.lower, self.upper = [], []
    def add(self, value):
        heappush(self.lower, -value)
        heappush(self.upper, -heappop(self.lower))
        if len(self.upper) > len(self.lower):
            heappush(self.lower, -heappop(self.upper))
    def median(self):
        if not self.lower:
            raise ValueError("No values")
        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])
        return (-self.lower[0] + self.upper[0]) / 2

stream = MedianFinder()
stream.add(2); assert stream.median() == 2
stream.add(8); assert stream.median() == 5
stream.add(5); assert stream.median() == 5

Work and storage: Insertion O(log n), median O(1), storage O(n).

When to recognize it: The median is the boundary between a lower max-heap and upper min-heap.

Check before applying it: Size balance alone is insufficient; cross-half ordering must also hold.

Add lazy deletion maps or balanced ordered multisets; heaps cannot remove arbitrary expired items directly.