Day 106-Q1 | Leftist Heap（左偏ヒープ）

問題

$N$個の値$A_1,\dots,A_N$が与えられる。最初、要素$i$（値$A_i$）はそれぞれ単独で1つのヒープを成している。以下の$Q$個のクエリを順に処理せよ。

1 x y: 要素$x$が属するヒープと要素$y$が属するヒープを1つに併合する。すでに同じヒープなら何もしない。
2 x: 要素$x$が属するヒープの最小値を出力し、そのヒープから取り除く。ヒープが空なら-1を出力。

すべてのクエリを$O((N+Q)\log N)$程度で処理せよ。Leftist Heap（左偏ヒープ）は、各ノードに「最も近い外部ノードまでの距離」distを持たせ、常に「左部分木のdist ≥ 右部分木のdist」を保つことで、木の右側の経路（右スパイン）の長さを$O(\log N)$に抑える。併合はこの右スパインだけをマージソート的に処理すればよい。

入力形式

N Q
A_1 A_2 ... A_N
query_1
...
query_Q

制約

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

$1 \le A_i \le 10^9$

クエリの$x,y$は$1\le x,y\le N$

入出力例

入力例1

出力例1

要素1,2を併合→$\{5,3\}$の最小値3を取出し残り$\{5\}$。要素3,4を併合→$\{8,1\}$の最小値1を取出し残り$\{8\}$。要素5は単独$\{9\}$→9を取出し空に。次の取出しは空なので-1。

概念図: 右スパインに沿った併合

ヒント（段階的開示）

ヒント1: 方向性

配列を毎回ソートし直す、ヒープを作り直すといった方法では併合のたびに$O(N)$かかる。heapqは追加・最小値取り出しは得意だが「2つのヒープを高速に併合する」操作が苦手。この併合を$O(\log N)$で行えるデータ構造が必要。

ヒント2: アプローチ

Leftist Heapは各ノードに「最も近い外部ノードまでの距離」distを持たせ、常に「左部分木のdist ≥ 右部分木のdist」を保つ。この性質により右スパインの長さは$O(\log N)$に抑えられる。併合は右スパイン同士をマージソート的に併合し、左右を必要に応じて入れ替えるだけで実現できる。「今どのヒープに属しているか」はUnion-Findで管理し、代表元に「現在のヒープの根ノード」を対応づける。

ヒント3: 誘導（コード骨格）

def merge(x, y):
    if x == 0: return y
    if y == 0: return x
    if val[x] > val[y]:
        x, y = y, x
    right[x] = merge(right[x], y)
    if dist[left[x]] < dist[right[x]]:
        left[x], right[x] = right[x], left[x]
    dist[x] = dist[right[x]] + 1
    return x
# Union-Find: find(x)でxのグループ代表元を取得。
# heap_root[代表元] = merge(...) の形で「今の根」を管理する。

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1

    val = [0] * (n + 1)
    left = [0] * (n + 1)
    right = [0] * (n + 1)
    dist = [0] * (n + 1)
    dist[0] = -1  # 番兵（空木）
    for i in range(1, n + 1):
        val[i] = int(data[idx]); idx += 1

    def merge(x, y):
        if x == 0:
            return y
        if y == 0:
            return x
        chain = []
        cx, cy = x, y
        while cx != 0 and cy != 0:
            if val[cx] > val[cy]:
                cx, cy = cy, cx
            chain.append(cx)
            cx = right[cx]
        tail = cx if cx != 0 else cy
        for node in reversed(chain):
            right[node] = tail
            if dist[left[node]] < dist[right[node]]:
                left[node], right[node] = right[node], left[node]
            dist[node] = dist[right[node]] + 1
            tail = node
        return tail

    parent = list(range(n + 1))
    rank_ = [0] * (n + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return rx
        if rank_[rx] < rank_[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank_[rx] == rank_[ry]:
            rank_[rx] += 1
        return rx

    heap_root = list(range(n + 1))

    out = []
    for _ in range(q):
        t = data[idx]; idx += 1
        if t == b'1':
            x = int(data[idx]); idx += 1
            y = int(data[idx]); idx += 1
            gx, gy = find(x), find(y)
            if gx == gy:
                continue
            rx, ry = heap_root[gx], heap_root[gy]
            new_root = merge(rx, ry)
            g = union(x, y)
            heap_root[g] = new_root
        else:
            x = int(data[idx]); idx += 1
            g = find(x)
            r = heap_root[g]
            if r == 0:
                out.append("-1")
            else:
                out.append(str(val[r]))
                heap_root[g] = merge(left[r], right[r])
    print("\n".join(out))


solve()

計算量: $O((N+Q)\log N)$（mergeは右スパインのみを辿るため木のサイズに対して対数時間。Union-Findはならし$O(\alpha(N))$）。ランダム500ケースでbrute-force集合シミュレーションと一致することを確認済み。

Step-by-Step 解説

1ノード構造
各要素をそのままノードとして使う。val/left/right/distを持ち、0は「空」を表す番兵（dist[0]=-1）。

2mergeの反復実装
右部分木を辿りながらchainに積み、逆順に処理して左偏性(dist[left]≥dist[right])を保つよう左右をswapする。右スパインだけを触るのでO(log N)。

3delete-minとinsertはmergeの特殊ケース
delete-minは根の値を出力し、left[root]とright[root]をmergeして新しい根にするだけ。

4Union-Findで所属管理
heap_root[代表元]に現在の根ノードを記録。ヒープmergeとDSU unionを必ずセットで行うことで、find(x)から現在のヒープに定数時間でアクセスできる。

よくあるミス

ミス	原因	正しい書き方
mergeを再帰のまま大きいNで実行	右スパインはO(log N)だがPythonの再帰上限に達しやすい	右スパインをリストに集め逆順処理する反復版にする
ヒープ併合時にUnion-Find側の併合を忘れる	heap_rootの参照先（代表元）がずれる	ヒープmergeとDSU unionを必ず同時に行う
heap_root[g]をunion前の代表元に書き込む	union後どちらが新代表元になるかはrank次第	union()の戻り値（新代表元）に対して更新する
空ヒープでの-1判定を忘れる	根ノードが0（番兵）かのチェック漏れ	heap_root[g]==0を必ず判定する

次のステップ

発展: k番目に小さい値を答えるクエリを追加する（平衡二分探索木との組み合わせが必要）
発展: Skew Heap（歪みヒープ）で同じ問題を解く（distを持たず常に左右入替えの単純実装）
次回予告: ISAP（Improved Shortest Augmenting Path・最大流のGap最適化）

自己評価

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

Day 106-Q1 — Leftist Heap（左偏ヒープ）

問題