二項ヒープ入門：概要・内部構造・主要操作と実装のコツを徹底解説
エバープレイ編集部二項ヒープとは — 概要
二項ヒープ（binomial heap）は、優先度付きキュー（priority queue）を実装するための木構造のデータ構造で、特に「ヒープの合併（meld／union）」操作を効率よく行える点が特徴です。1978年に Jean Vuillemin によって提案された二項ヒープは、二項木（binomial tree）と呼ばれる特別な完全木群の集合（森）として表現され、木の次数（根の子の数）がすべて異なるように管理されます。
基本的な性質と直感
- 二項木 Bk の性質：次数 k の二項木 Bk は、ノード数が 2^k、深さ（高さ）は k であり、各レベルに二項係数に対応するノード数を持ちます。特に Bk は、Bk−1 を根の子として付け替えることにより構成できます。
- 森としての表現：二項ヒープは互いに次数が異なる二項木の集合（根の連結リスト）として表されるため、ノード総数 n は二項木の次数の 2 の冪の和として一意に表現できます。これは n の二進法表記と対応します。
- 根リストの順序：通常、根リストは次数の昇順（0,1,2,…）に整列して保持され、同じ次数の木が2つ以上あれば、それらを結合して次数を増やす（リンクする）ことで木集合の整合性を保ちます。
内部表現（ノード構造）
典型的なノードは以下のフィールドを持ちます：
- key（優先度）
- degree（次数＝子の数）
- parent（親へのポインタ）
- child（最初の子へのポインタ）
- sibling（兄弟（次の根または次の子）へのポインタ）
この表現により、根リストや各ノードの子リストは単方向連結リストで管理できます。
主要操作とアルゴリズム（要点と計算量）
以下では、代表的な操作とその計算量（n をヒープ中の要素数とする）を示します。ここでは CLRS（Introduction to Algorithms）で示される標準的な解析に基づきます。
- Make-Heap（空ヒープの作成）：Θ(1)
- Find-Min（最小要素の探索）：根リストをスキャンして最小 key の根を見つける。計算量は Θ(log n)（根の数は O(log n)）。
- Union（合併／meld）：2 つのヒープの根リストを次数順にマージし、同じ次数の二項木が隣接している場合はリンク操作で結合して整列を保つ。計算量は Θ(log n)。
- Insert（挿入）：新しい要素を単独の二項木（次数 0）として作り、それを既存ヒープと Union する。標準実装では Θ(log n)。
- Extract-Min（最小要素の削除）：根リストから最小根を取り除き、その子のリストを逆順にして新しいヒープを作成し、残りのヒープと Union する。計算量は Θ(log n)。
- Decrease-Key（キーの減少）：対象ノードのキーを減らし、親とのヒープ順序を満たすまでキーを親と交換しながら上に移動する。計算量は Θ(log n)。
- Delete（任意要素の削除）：Decrease-Key を使って対象キーを −∞ に更新し、続けて Extract-Min を呼ぶ。計算量は Θ(log n)。
まとめると、二項ヒープの主要操作は概ね Θ(log n) の時間で実行できます（Make-Heap は Θ(1)）。Find-Min が O(log n) である点は、配列ベースの二分ヒープ（binary heap）と異なり O(1) ではないことに注意してください。
Union（合併）の詳細（動作イメージ）
二項ヒープの核となる操作は合併です。手順の概略は次の通りです：
- 二つのヒープの根リストを次数順にマージ（マージ操作はマージソートの片割れのように線形時間で行える）。
- マージしたリストを一度走査して、隣接する根の次数が同じ場合にそれらをリンクする。リンクでは、キーが小さい方を新しい根とし、もう一方をその子として付ける（次数がひとつ増える）。
- 必要に応じてさらに連続した等次数の木が現れるため、走査を続けて整合性を保つ。
この操作が効率的なため、二項ヒープは「ヒープの合併」が頻発するアルゴリズム（例えば複数の優先度付きキューの頻繁な結合を伴う処理）に適しています。
Extract-Min の詳細
Extract-Min の核心は「最小根の削除」と「その根の子を新しいヒープとして再統合」することです。具体的には：
- 根リストを走査して最小 key の根 r を見つける。
- r を根リストから取り除き、r の子リストを逆順にたどって新しいヒープ H' を構築する（逆順にすることで次数の昇順を保てる）。
- 残ったヒープと H' を Union して新たなヒープを得る。
どの操作も根の数に比例（O(log n)）するため、Extract-Min は Θ(log n) となります。
Decrease-Key と Delete の扱い
Decrease-Key は、対象ノードのキーを小さくした後、ヒープ順序を満たすまで親とのキー交換を繰り返す（バブルアップ）という非常に単純な操作です。Fibonacci ヒープのようにカットを複雑に扱って amortized O(1) にする手法は用いられません。Delete は Decrease-Key（キーを十分小さく）→ Extract-Min の組合せで実現します。
実装上のコツと注意点
- 根リストや子リストはポインタ（sibling）で単方向連結リストにすると実装が簡潔です。
- Union の際、マージ→連結走査→リンクの順番を間違えるとループや次数の矛盾が発生するので注意すること。
- キー交換で Decrease-Key を実装する場合、ノードの識別子（ハンドル）を保持しておくと簡単に任意ノードを操作できる。配列ベースのヒープと違い、ノード位置が固定されないためハンドル方式が便利です。
- メモリ管理（親ポインタの更新、子リストの逆順化など）を丁寧に行う必要があります。特に Extract-Min のときの子リスト逆順化は見落としやすいポイントです。
二項ヒープと他のヒープとの比較
- Binary heap（二分ヒープ）：配列ベースで実装が簡単。Find-Min は O(1)、Insert/Extract/Decrease-Key は O(log n)。しかし Heap の合併は O(n) と非効率。合併が重要なら二項ヒープに分がある。
- Fibonacci heap：Fredman & Tarjan による改良で、amortized な解析により Decrease-Key を O(1) にでき、合併も O(1)（amortized）。アルゴリズム理論上は最速に近いが、実装は複雑で定数因子も大きい。
- Pairing heap 等の単純な実装：実装が比較的簡単で実用上高速なことが多く、二項ヒープやフィボナッチヒープよりも現実的な選択になるケースも多い。
適用例と選択基準
二項ヒープは「ヒープの合併を頻繁に行う」アルゴリズムや、実装の複雑さと機能のバランスを重視する場合に向きます。具体例としては、複数の優先度付きキューをマージしながら進めるグラフアルゴリズムや、機能的（イミュータブル）な環境での実装が挙げられます。一方、減少キー操作が非常に多く、理論的最良の漸近時間を求めるなら Fibonacci ヒープを検討しますが、実装の複雑さと実行定数を考慮する必要があります。
まとめ
二項ヒープは、二項木という数学的にきれいな性質を利用して「合併」を効率的に行えるヒープです。ほとんどの基本操作が Θ(log n) で行える一方、実装は比較的直感的で、用途によっては非常に有用なデータ構造です。フィボナッチヒープほどの amortized な高速性はないものの、実装の容易さと合併性能のトレードオフから、今でも教育的・実務的に価値のある選択肢です。
参考文献
- Binomial heap — Wikipedia (英語)
- Binomial Heap — GeeksforGeeks（実装例と解説）
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 3rd Edition（CLRS） — MIT Press
投稿者プロフィール
