中央値

中央値

median

上半分小さい順と下半分大きい順のキューを用意。交互につっこんで、上半分の最小値が下半分の最大値を超えてる時は入れ替える

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)