Find Median from Data Stream

import heapq

class MedianFinder:
    def __init__(self):
        self.low, self.high = [], []   # max (negated), min
    def addNum(self, num):
        if not self.low or num <= -self.low[0]:
            heapq.heappush(self.low, -num)
        else:
            heapq.heappush(self.high, num)
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
    def findMedian(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Find Median from Data Stream. Numbers arrive one at a time, and we must report the median so far.

Take five, fifteen, one and three. Sorted, that's one, three, five, fifteen. Two middle values, three and five, so the median is their average: four.

The simple way keeps a sorted list. Reading the middle is instant, but each new number shifts everything after it. That's O of n per add.

But we only need the middle. So split the numbers into two halves. The lower half is a max heap, its biggest on top. The upper half is a min heap, its smallest on top. The two tops meet at the middle. Keep them balanced: equal, or the low side one bigger.

In code, Python's heap is a min heap, so the low side stores negatives. Push onto the low side if the number is at most its top, otherwise onto the high side. If a side gets too heavy, pop its top across. Find median just reads the tops.

Let's add five: low side, median five. Fifteen goes high: median ten. One goes low: five. Three goes low too, and now low is two ahead, so its top, five, slides across. The median is three plus five over two: four. Eight goes high, that side is heavier, so five slides back. Median five.

Each add is a few heap moves: O of log n. The median reads two tops: O of one. And O of n space.

Two halves, two heaps, balanced on the middle. That's Find Median from Data Stream.