[白俊][Python]1665号説の真ん中

💡 しょかい
最初はこれが規則的な問題だと思って、最大和を実現し、お尻の要素の半分のpopで中間値を探しました.->タイムアウト
本当に分からないので、方法を探しました.最大ヒップと最小ヒップは使用されていますが、最大ヒップの実装ではtupleが使用され、値を変更する必要があるためエラーが発生しました.->ランタイムエラー(タイプエラー)
📝 解答方法
1回目の解法でタイムアウトが発生したため,バイナリ探索ツリーのようにルートを中間値にしようとしたが,左の小さい値の右に大きな値を入れたが,分類は優先順位キューであり,そうではないようなので検索した.
まず、ルートは中間値でなければなりません.次に、ルートを基準にして、左側にルートより小さい値、右側にルートより大きい値を配置します.このとき、左が最大のお尻、右が最小のお尻となります.(中間値がルートなので)
問題について
「この間白俊が叫んだ数が偶数だったら、真ん中の2つの数の中で小数を言うべきだ」
この文はとても重要で、2つの数の中で1つの小数を言い出すので、根を左の最大のお尻に編入します.すなわち,中間値は左最大ヒップの根である.
与えられた値を左ヒップ->右ヒップの順に順番に入れます.左臀部に先に置くのは、左臀部の根元が中間値になっているためです.例えば、[5,4,3,2,1]と入力すると
左[5]
右側[0]
左[5]
右側[4]
左[5,3]
右側[4]
左[5,3]
右側[2,4]
そうです.ただし、右臀部の数は左臀部の数より大きくなければならないので、右臀部の根は最小値、左臀部の根は最大値となるので、2つの値を比較し、右臀部の根の値が左前頭の根の値より小さい場合は、2つの数を交換してhip化する.簡単に交換すれば、エラー処理されます.
💡 ソースコード

import sys, heapq
input = sys.stdin.readline

def insertNum(num):
    temp_right = 0
    temp_left = 0
    if len(left_max_heap)==len(right_min_heap):
        heapq.heappush(left_max_heap, [(-1)*num, num])
    else:
        heapq.heappush(right_min_heap, num)

    if right_min_heap:
        if left_max_heap[0][1] > right_min_heap[0]:
            temp_right = heapq.heappop(right_min_heap)
            temp_left = heapq.heappop(left_max_heap)[1]
            heapq.heappush(right_min_heap, temp_left)
            heapq.heappush(left_max_heap, [(-1)*temp_right, temp_right])

N = int(input())
left_max_heap = []
right_min_heap = []

for i in range(N):
    num = int(input())
    insertNum(num)
    print(left_max_heap[0][1])