C++で学ぶ二項ヒープ（Binomial Heap）の基礎と操作

二項ヒープ（Binomial Heap）とは、二分ヒープ（Binary Heap）を拡張したデータ構造です。二分ヒープが提供する各種操作に加えて、より高速なマージ（union）操作を実現できる点が大きな特徴です。

二項ヒープは、複数の二項木（Binomial Tree）のコレクションとして表現されます。

二項木（Binomial Tree）とは？

次数kの二項木は、次数k-1の二項木を2つ用意し、一方をもう一方の最左の子として連結することで構築できます。

次数kの二項木には、以下のような性質があります。

• ノードの総数は正確に2^k個である。

• 木の深さはkである。

• 深さi（i = 0, 1, ..., k）には、正確にkCi個のノードが存在する。

• 根の次数はkであり、根の子は左から右へ順に、次数k-1, k-2, ..., 0の二項木として扱われる。

二項ヒープの定義

二項ヒープは、それぞれの二項木が最小ヒープの性質（Min Heap Property）を満たすような、二項木の集合として定義されます。また、同じ次数を持つ二項木は最大でも1本しか存在できません。

以下は二項ヒープの例です。

12個のノードを持つ二項ヒープ。これは2本の二項木のコレクションとして扱われます。

左から右へ、次数2と次数3の二項木で構成されています。

二項ヒープと数の2進表現の関係

m個のノードを持つ二項ヒープにおいて、二項木の本数はmの2進表現におけるセットビット（1になっているビット）の数と一致します。

例えば、m = 13の場合、13の2進表現は00001101となり、セットビットは3つあります。これは、二項ヒープが3本の二項木で構成されていることを意味します。

さらに、これらの二項木の次数をセットビットの位置と対応付けることも可能です。この関係から、m個のノードを持つ二項ヒープにはO(log m)本の二項木が含まれると結論付けることができます。

二項ヒープの主要な操作

二項ヒープにおいて、union()は最も重要な操作であり、他のすべての操作は基本的にこの操作を利用して実装されます。union()は、2つの二項ヒープを1つに統合する役割を担います。

• insert(h, K)：キー「K」を二項ヒープ「h」に挿入します。まず、キー「K」のみを含む単一ノードの二項ヒープを作成し、次にhと新しい二項ヒープに対してunionを呼び出します。

• getMin(h)：最もシンプルな方法は、各二項木の根のリストを走査し、最小のキーを返すことです。この方法にはO(log m)の時間がかかります。ただし、最小キーを持つ根へのポインタを常に保持しておくことで、計算量をO(1)まで改善できます。

• extractMin(h)：この操作もunion()を利用します。まずgetMin()を呼び出して最小キーを持つ二項木を特定し、次にそのノードを削除します。そして、削除したノードのすべての部分木を結合して新しい二項ヒープを作成します。最後に、元のヒープhと新しく作成した二項ヒープに対してunion()を呼び出します。この操作にはO(log m)の時間が必要です。

• delete(h)：二分ヒープと同様に、まず対象のキーを負の無限大に変更し、その後extractMin()を呼び出すことで削除を実現します。

• decreaseKey(h)：こちらも二分ヒープと同じ考え方です。減らしたキーを親ノードのキーと比較し、親のキーの方が大きい場合はキーを交換して、親に対して再帰的に同じ処理を繰り返します。親のキーが小さいノードに到達するか、根ノードに到達した時点で処理を終了します。decreaseKey()の時間計算量はO(log m)です。

まとめ

二項ヒープは、通常の二分ヒープではO(m)かかるヒープ同士のマージ（union）をO(log m)で高速に行える強力なデータ構造です。優先度付きキューの統合が頻繁に発生する場面や、グラフアルゴリズムの高度な実装などで威力を発揮します。C++での実装においても、ポインタによる木構造の管理と再帰的な統合処理を理解することが、効率的な活用への鍵となります。