ALDS1_9_C: Priority Queue (続き)

やっぱり末尾から持ち上げていく感じ？

でとりあえず書いてみた・・・

def insert(S, k):
    def rec(i):
        nonlocal S

        if i == 1:
            return

        p = parent_node(i)
        if S[p] < S[i]:
            swap(S, p, i)
            rec(p)

    S.append(k)
    rec(last_node(S))

def extract_max_old(S):
    def rec(i, k):
        nonlocal S

        if i == 1:
            tmp = S[i]
            S[i] = k
            return tmp

        parent = parent_node(i)
        sibling = sibling_node(i)
        larger = i if S[i] > S[sibling] else sibling
        tmp = S[larger]
        S[larger] = k
        return rec(parent, tmp)

    last = last_node(S)
    if last == 1:
        return S.pop()

    parent = parent_node(last)
    if is_left(last):
        return rec(parent, S.pop())
    else:
        left = left_node(parent)
        if S[left] > S[last]:
            v = S[left]
            S[left] = S.pop()
            return rec(parent, v)
        else:
            return rec(parent, S.pop())

んだけどこれではextract_maxの場合分けが全く足りてない
というかほとんど破綻している
insertはたぶん大丈夫

ということでextract_maxを絵に描きながら考えてたら、
先頭をただ削除するんじゃダメだけど、
末尾の項目を先頭にコピーして、一回だけmax_heapifyしたらいけんじゃね？
と思った

こう

def extract_max(S):
    if last_node(S) == 1:
        return S.pop()
    else:
        k = S[1]
        S[1] = S.pop()
        max_heapify(S, 1)
        return k

この間味をしめたデタラメテストによるとこれで動いてる
オーダもlog(n)のオーダだし

というわけでジャッジ！
TLE！

すみません解説見ます