Pythonでアルゴリズム(中央値)

目的

1つのサイズ$ N $のリストの中央値を求める際の計算量はソートしてから求めることで$ O(NlgN) $。($ O(N) $でも可能。)
しかし、リストの長さがクエリごとに変化する場合には毎回ソートして中央値を求めると計算量が非常に大きくなってしまう。($ k $回目で$ O(klgk) $でそれを$ k=1からN $まで行う)
この操作を$ k $回目で$ O(lgk) $で済むようによう改善する。

方法

・現在の中央値より小さい値をリスト$ left $に、大きい値をリスト$ right $に格納する。この際、$ left $からは最大値、$ right $からは最小値を常に$ O(lgN) $(リストの長さが$ N $のとき)で取り出せるように$ left $はMax優先度付きキュー、$ right $はmin優先度付きキューにする。
・値を挿入する際には、$ left $の最大値と$ right$ の最小値と比較してこれら3要素を大小関係に基づき$ left $と$ right $ の要素数が均等になるよう割り振る(合計が奇数個の場合は$ left $を1つ分多くする)
・中央値は合計が奇数個の場合は$ left $の最大値、偶数個の場合は$ left $の最大値と$ right $の最小値が中央値になる

実装

・入力は要素数$ N $と$ N $個の要素を持つ配列$ A $
・出力は$ k $行目に$ k $番目の要素を挿入したあとの中央値

from heapq import heappush, heappop

# 入力
n = int(input())
a = [int(x) for x in input().split()]

# 番兵
left = [float('inf')]
right = [float('inf')]

for i in range(n):
    left_max = -left[0] # leftの最大値
    right_min = right[0] # rightの最小値
    if len(left) == len(right):
        if a[i] > right_min:
            heappush(left, -heappop(right))
            heappush(right, a[i])
        else:
            heappush(left, -a[i])
    else:
        if a[i] < left_max:
            heappush(right, -heappop(left))
            heappush(left, -a[i])
        else:
            heappush(right, a[i])
    if len(left) > len(right):
        print(-left[0])
    else:
        print(-left[0], right[0])