# 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

``````