Day 111-Q1 | Pairing Heap（ペアリングヒープ）

問題

空の優先度付きキュー（最小値取り出し）に対して、$Q$ 個のクエリを順に処理せよ。クエリは 0 x（値 $x$ を挿入）と 1（最小値を取り出して出力）の2種類。クエリ 1 が来る時点でキューは空でないことが保証される。

入力形式

Q
query_1
query_2
...
query_Q

制約

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

$-10^9 \le x \le 10^9$

クエリ1実行時、キューは必ず非空

入出力例

入力例1

出力例1

3
1
5

$\{5,3,8\}$ 挿入後、最小値 $3$ を取り出す→$\{5,8\}$。$1$ を挿入し最小値 $1$ を取り出す→$\{5,8\}$。最後に $5$ を取り出す。

概念図: merge と 2-passマージ

ヒント（段階的開示）

ヒント1: 方向性

二分ヒープは insert・extract-min ともに $O(\log N)$。insert が支配的な操作列では、insert をほぼ $O(1)$ にできる構造が有利になる。「2つのヒープをマージする」ことを基本操作とする多分岐ヒープ順木（left-child right-sibling表現）を考える。

ヒント2: アプローチ

merge(A,B): 根同士を比較し、値が大きい方を、小さい方の「最初の子」として連結する。$O(1)$。insert(x) は単一ノードのヒープを既存ヒープに merge するだけ。extract-min は根を消すと残る「子の連結リスト」を、左から2つずつペアで merge する1st passと、その結果を右から左へ畳み込む2nd passの2-passマージで1本に戻す。これにより償却 $O(\log N)$ が保証される。

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

def merge(a, b):
    if a is None: return b
    if b is None: return a
    if a.val > b.val:
        a, b = b, a
    b.sibling = a.child
    a.child = b
    return a
# extract-minでは merge_pairs(root.child) を新しい根にする
# merge_pairs は再帰よりも配列に展開してからループで2-passマージする方が安全（子の数がO(N)になりうるため）

模範解答 (Python)

import sys

class Node:
    __slots__ = ("val", "child", "sibling")
    def __init__(self, val):
        self.val = val
        self.child = None
        self.sibling = None

def merge(a, b):
    if a is None:
        return b
    if b is None:
        return a
    if a.val > b.val:
        a, b = b, a
    b.sibling = a.child
    a.child = b
    return a

def merge_pairs(node):
    if node is None:
        return None
    lst = []
    while node:
        nxt = node.sibling
        node.sibling = None
        lst.append(node)
        node = nxt
    merged = []
    i = 0
    while i + 1 < len(lst):
        merged.append(merge(lst[i], lst[i + 1]))
        i += 2
    if i < len(lst):
        merged.append(lst[i])
    result = None
    for h in reversed(merged):
        result = merge(h, result)
    return result

def solve():
    data = sys.stdin.read().split()
    idx = 0
    q = int(data[idx]); idx += 1
    root = None
    out = []
    for _ in range(q):
        t = data[idx]; idx += 1
        if t == "0":
            x = int(data[idx]); idx += 1
            root = merge(root, Node(x))
        else:
            out.append(str(root.val))
            root = merge_pairs(root.child)
    print("\n".join(out))

solve()

計算量: insertは $O(1)$、extract-minは償却 $O(\log N)$（2-passマージのポテンシャル解析による）。$Q=2\times10^5$ 個の混在クエリで heapq 参照実装と全出力一致を確認済み。再帰を使わない配列ベース実装のため、挿入過多パターンでも RecursionError にならないことも確認済み。

Step-by-Step 解説

1ノード表現を決める
「最初の子」「次の兄弟」の2ポインタだけを持つ多分岐木で任意個の子を扱う。

2merge を $O(1)$ で実装する
値が大きい方の根を小さい方の子として追加するだけ。木の形は一切気にしない。

3insert を merge の特殊形にする
単一ノードのヒープを既存ヒープに merge するだけで済む。

4extract-min で2-passマージを行う
子の連結リストをペアで merge する1st pass、右から左へ畳み込む2nd passの2段階で1本のヒープに戻す。これが償却 $O(\log N)$ の鍵。

5再帰を避けて安全に実装する
子の数が最悪 $O(N)$ になりうるため、配列展開＋ループで merge_pairs を書く。

よくあるミス

ミス	原因	正しい書き方
子を左から順に1つずつ merge する	実装は簡単だが最悪ケースで $O(N)$ になり償却保証が崩れる	必ず2-passマージ（ペア→右から左へ畳込み）を使う
`merge`の大小比較を誤る	ヒープ順の定義を取り違える	値が大きい方を、小さい方の子として連結する
`merge_pairs`を再帰で実装し`RecursionError`	子の数が最悪$O(N)$になりうることを見落とす	配列に展開してからループで2-passマージする
展開時に古い`sibling`を消し忘れる	古いポインタが残ると後続のmergeでループ構造が壊れる	展開時に`node.sibling=None`を明示的に設定する

次のステップ

発展: decrease-key をサポートする完全版に拡張する（ダイクストラ法の高速化に使われる）
発展: Fibonacci Heap（Day082）との償却計算量の違いを比較する
発展: 複数の集合をマージしながら最小値を管理するオンラインクエリに応用する

自己評価

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

Day 111-Q1 — Pairing Heap（ペアリングヒープ・2-passマージによる償却計算量）

問題