Day 17 - Running median


Definition(s)

We will use a max heap for storing data of the smaller half of the numbers and a min heap for storing data of the larger half of the numbers.

Algorithm(s)


In [1]:
from heapq import heappop, heappush, heappushpop

In [2]:
def running_median(xs):
    low, high = [], []
    
    for x in xs:
        if not high:
            heappush(high, x)
        else:
            if len(high) > len(low):
                if x > high[0]:
                    heappush(low, -heappushpop(high, x))
                else:
                    heappush(low, -x)
            else:
                if x < -low[0]:
                    heappush(high, -heappushpop(low, -x))
                else:
                    heappush(high, x)
                    
        if len(high) > len(low):
            print(high[0])
        else:
            print((-low[0] + high[0]) / 2)

Run(s)


In [3]:
running_median([12, 4, 5, 3, 8, 7])


12
8.0
5
4.5
5
6.0

In [4]:
running_median(range(10))


0
0.5
1
1.5
2
2.5
3
3.5
4
4.5

In [5]:
running_median(reversed(range(5)))


4
3.5
3
2.5
2

In [6]:
running_median([12, 6, 1, 30, 8, 72])


12
9.0
6
9.0
8
10.0