ペアリングヒープとは？特徴・基本操作・計算量をわかりやすく解説

ペアリングヒープとは

ペアリングヒープ（Pairing Heap）は、比較的シンプルな実装でありながら、実用上きわめて優れた償却性能（amortized performance）を発揮することで知られるヒープデータ構造の一種です。

ペアリングヒープは「ヒープ順序」を満たす多分木構造として定義され、簡略化されたフィボナッチヒープとみなすこともできます。

プリム法（Primの最小全域木アルゴリズム）のようなアルゴリズムを実装する際の「堅牢な選択肢」とされており、最小ヒープを前提とした場合、以下の操作をサポートします。

ペアリングヒープの主な操作

• find-min（最小値の参照） − ヒープの先頭にある要素（最小要素）を返します。
• meld（併合） − 2つの根の要素を比較し、小さい方を結果の根とします。大きい方の要素とその部分木は、この根の子として追加されます。
• insert（挿入） − 挿入対象の要素だけで新しいヒープを作成し、それを元のヒープに併合（meld）します。
• decrease-key（キーの減少・任意） − 減少させたいキーを根とする部分木をヒープから切り離し、そのキーをより小さな値に置き換えた上で、再びヒープへ併合します。
• delete-min（最小値の削除） − 根を取り除いた後、その部分木同士を繰り返し併合し、最終的に1つの木だけが残るまで処理を続けます。この際には様々なマージ戦略が用いられます。

データ構造の表現方法

各ノードは左側の子へのポインタを持ち、さらに左側の子は自身の次の兄弟ノードへのポインタを保持します。この「左の子・右の兄弟」という表現方式により、多分木を効率的に扱うことができます。

以下はペアリングヒープの構造例です。

計算量の分析

ペアリングヒープの計算量に関する解析は、スプレー木（Splay Tree）の解析手法に着想を得て発展しました。

償却計算量の観点では、delete-min は O(log n) と評価されており、find-min・meld・insert の各操作は O(1) の償却時間で実行できるとされています。理論的な厳密な解析には未解決の部分があるものの、実用面での高いパフォーマンスから多くの場面で採用されています。