How do you find the median of a stream of numbers as they arrive?
You keep two heaps. One holds the smaller half of the values and one holds the bigger half, and the two of them are always in balance.
import heapq
class MedianFinder:
def __init__(self):
self.lower = []
self.upper = []
def add(self, value):
heapq.heappush(self.lower, -value)
heapq.heappush(self.upper, -heapq.heappop(self.lower))
if len(self.upper) > len(self.lower):
heapq.heappush(self.lower, -heapq.heappop(self.upper))
def median(self):
if len(self.lower) > len(self.upper):
return -self.lower[0]
return (-self.lower[0] + self.upper[0]) / 2
So how does it work? The lower heap is a max heap, so the biggest of the smaller half is at its front. The upper heap is a min heap, so the smallest of the bigger half is at its front. And the two heaps are kept the same size, or with the lower one having one more.
And the add method does three things. It puts the new value in the lower heap. Then it moves the biggest value of the lower heap up into the upper heap, which makes sure the lower half is all smaller than the upper half. And then, if the upper heap has one too many, it moves the smallest of the upper heap down into the lower heap, which balances the sizes.
the values added the lower heap the upper heap the median
----------------- -------------- -------------- ---------
5 [5] [] 5
3 [3] [5] 4
8 [3, 5] [8] 5
1 [1, 3] [5, 8] 4
And the median comes from the tops. With an odd number of values the lower heap has one more, so the median is the top of the lower heap. With an even number the heaps are the same size, so the median is the average of the two tops.
And the complexity is O of log n for each add and O of 1 for the median, and O of n for the space.
So the rule to remember is this. The lower heap is stored with the values turned round, so that the smallest stored value is the biggest real value.
The last question in this topic shows how to handle removing values.