中央値

from heapq 中央値

• median
• 上半分小さい順と下半分大きい順のキューを用意。交互につっこんで、上半分の最小値が下半分の最大値を超えてる時は入れ替える 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)
        if -lower[0] > upper[0]:
            l = -lower[0]
            u = -upper[0]
            heapreplace(lower, u)
            heapreplace(upper, l)
            print(upper, lower)
print(upper[0], -lower[0])  # => 5 4