Two heaps (running median)

The two-heaps pattern keeps a dividing line through the data. The 'low' heap is a max-heap holding the smaller half, so its top is the largest of the small numbers. The 'high' heap is a min-heap holding the larger half, so its top is the smallest of the large numbers. Those two tops sit right next to the middle.

Two invariants make it work: every number in low is less than or equal to every number in high, and the sizes differ by at most one (here, low may have one extra). With an odd count the median is low's top; with an even count it is the average of both tops.

The same idea applies whenever you need fast access to the boundary between two groups, such as the best affordable project in the IPO problem or a percentile other than 50%.

1. 1Keep low (max-heap, stored as negatives in Python) and high (min-heap).
2. 2To add x: push it into low. Then pop low's largest and push it into high. This step guarantees every item in low is <= every item in high, even if x belonged in the upper half.
3. 3Rebalance: if high now has more items than low, pop high's smallest and push it back into low. Now low has the same number of items as high or one more.
4. 4Median: if low is bigger, return low's top. Otherwise return the average of low's top and high's top.
5. 5Each add does a constant number of heap operations, so it is O(log n); reading the median is O(1).

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []     # max-heap of the smaller half (values stored negated)
        self.high = []    # min-heap of the larger half

    def add(self, x):                                   # O(log n)
        heapq.heappush(self.low, -x)
        # move the largest of the low half up, so every low <= every high
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):              # low keeps the extra item
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):                                   # O(1)
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Every new number goes into low, then low's largest is moved to high, which keeps the ordering invariant. If high becomes bigger, its smallest moves back, so low always has equal size or one extra. The median is low's top for an odd count and the average of the tops for an even count.

Cost: add O(log n), median O(1), space O(n). Sliding window median with lazy deletion: O(n log n) overall (stale entries can briefly keep heaps larger than k).