median

median

median

Prepare queues in order of smallest upper half and largest lower half. Alternate the queues, and if the minimum value of the upper half exceeds the maximum value of the lower half, swap the queues.

code:python

from random import shuffle

xs = list(range(10))

shuffle(xs)

upper = []

lower = []

for i, x in enumerate(xs):

if i % 2 == 0:

heappush(upper, x)

else:

heappush(lower, -x)

print(upper, lower)

heapreplace(lower, u)

heapreplace(upper, l)

print(upper, lower)

---