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)


    

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