Day 136-Q1 | Skew Heap（自己調整型マージ可能ヒープ）

問題

$N$ 個のヒープ（番号 $1$ から $N$）があり、はじめすべて空である。以下の3種類のクエリを $Q$ 個、順番に処理せよ。

0 t x : ヒープ $t$ に整数 $x$ を1つ追加する。
1 t : ヒープ $t$ の最小値を出力し、そのヒープから取り除く。ヒープ $t$ が空なら -1 を出力する。
2 t1 t2 : ヒープ $t2$ の要素をすべてヒープ $t1$ に移す（マージする）。マージ後、ヒープ $t2$ は空になる。

「合体可能ヒープ（mergeable heap）」を rank（npl）を一切管理しない Skew Heap で実装し、全クエリを合計 $O(Q \log N)$ 償却で処理せよ。

入力形式

N Q
query_1
...
query_Q

制約

$1 \le N, Q \le 2\times10^5$

$0 \le x \le 10^9$

クエリ2では $t1 \ne t2$

入出力例

入力例1

出力例1

3
5

入力例2

出力例2

-1
100

概念図

ヒント（段階的開示）

ヒント1（方向性）

Leftist Heap は npl（null path length）を持たせて「軽い方を右に」というルールで木の右側の深さを抑える。npl の管理なしで、同じ償却 $O(\log N)$ を達成する単純なルールはないだろうか。

ヒント2（アプローチ）

Skew Heap は「マージのたびに、通った経路上のノードの左右の子を無条件で入れ替える」だけ。npl や高さの情報は一切持たない。ヒープ番号ごとに「根へのポインタ」だけ管理すれば、追加・取り出し・統合のすべてが merge 関数1つに帰着する。

ヒント3（誘導）

def merge(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    if val[a] > val[b]:
        a, b = b, a
    right[a] = merge(right[a], b)
    left[a], right[a] = right[a], left[a]  # 無条件 swap
    return a

追加は root[t] = merge(root[t], new_leaf)、最小値取り出しは左右の子を merge、統合は2つの根を merge するだけで実装できる。

模範解答 (Python)

import sys


def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1

    sys.setrecursionlimit(1 << 20)

    max_nodes = Q + 1
    val = [0] * max_nodes
    left = [0] * max_nodes
    right = [0] * max_nodes
    node_count = 0

    root = [0] * (N + 1)

    def merge(a, b):
        if a == 0:
            return b
        if b == 0:
            return a
        if val[a] > val[b]:
            a, b = b, a
        right[a] = merge(right[a], b)
        left[a], right[a] = right[a], left[a]
        return a

    out = []
    for _ in range(Q):
        t = int(input_data[idx]); idx += 1
        if t == 0:
            tid = int(input_data[idx]); idx += 1
            x = int(input_data[idx]); idx += 1
            node_count += 1
            val[node_count] = x
            left[node_count] = 0
            right[node_count] = 0
            root[tid] = merge(root[tid], node_count)
        elif t == 1:
            tid = int(input_data[idx]); idx += 1
            r = root[tid]
            if r == 0:
                out.append("-1")
            else:
                out.append(str(val[r]))
                root[tid] = merge(left[r], right[r])
        else:
            t1 = int(input_data[idx]); idx += 1
            t2 = int(input_data[idx]); idx += 1
            root[t1] = merge(root[t1], root[t2])
            root[t2] = 0

    print("\n".join(out))


main()

Step-by-Step 解説

1ノードを配列で管理する
Python でオブジェクトを毎回生成すると遅いので、val・left・right の3配列で表現する。インデックス0を「空」として予約する。

2merge が全操作の基盤
追加・最小値取り出し・統合のすべてが merge 1つに帰着し、実装が大幅に単純化される。

3無条件swapの意味
Leftist Heapの条件付きswapと違い、Skew Heapは毎回無条件にswap。償却解析（ポテンシャル=重いノードの個数）により全体で $O(Q\log N)$ が保証される。

4マージ後にヒープを空にする
root[t1]=merge(...)の後、root[t2]=0として明示的に空にすることで、以降t2への追加が独立ヒープとして扱われる。

5償却計算量の直感
1回のマージの実際のコストは最悪 $O(N)$ になり得るが、swapによる「軽い部分木⇔重い部分木」の切り替えがポテンシャルの増減で相殺され、全体で $O(Q\log N)$ に収まる。

よくあるミス

ミス	原因	正しい書き方
再帰の深さ制限に引っかかる	マージ経路長が最悪O(N)になり得る	`sys.setrecursionlimit`を十分大きく設定する
ノード配列のサイズ不足	追加クエリの数だけノードが生成される	配列を `Q+1` 以上で確保する
マージ後に`root[t2]`を空にし忘れる	古いポインタが残り要素が重複扱いされる	統合処理の最後に必ず `root[t2]=0`
npl（rank）を管理してしまう	Leftist Heapの実装と混同	Skew Heapでは追加フィールド不要。無条件swapのみ
空ヒープからの取り出しで例外	`root[t]==0`時に`val[root[t]]`参照	取り出し前に空チェックし`-1`を出力

次のステップ

発展: Skew Heap に decrease-key を追加するのは難しい。外部ポインタ保持方式や Pairing Heap との比較を検討せよ。
発展2: マージクエリをUnion-Findのグループ管理に変え、根の代表IDだけ付け替える実装と比較せよ。

自己評価

完全理解おおむね理解要復習

Day 136-Q1 — Skew Heap（自己調整型マージ可能ヒープ）

問題