C++で学ぶ二項ヒープのメモリ表現 ― 二項木の構造とノードの5つのフィールド

二項木（Binomial Tree）とは？

二項木とは、順序木データ構造の一種です。最小の二項木 B0 は単一のノードで構成され、一般に Bk で表される二項木は、2つの Bk-1 の二項木を連結したものになります。このとき、片方の二項木の根は、もう片方の二項木の根の左端の子として接続されます。この性質により、次数 k の二項木は必ず 2^k 個のノードを持ちます。

なお、「二項木」という名前は金融分野のオプション価格評価（二項モデル）でも登場しますが、本記事で扱うのはデータ構造としての二項木・二項ヒープであり、主に優先度付きキューの効率的な実装に活用されます。

二項ヒープ（Binomial Heap）とは？

二項ヒープとは、複数の二項木を組み合わせて構成されるデータ構造です。挿入・削除・マージといった操作を対数時間で効率的に行えるため、優先度付きキューの実装に非常に適しています。

二項ヒープ H が満たすべき性質は以下の2点です。

• H 内のすべての二項木はヒープ順序に従います。つまり、任意のノードのキーは、その親ノードのキー以上になります。

• H には、同じ次数（degree）を持つ二項木は最大で1つしか存在しません。

二項ヒープの例

二項ヒープノードのメモリ表現

二項ヒープの各ノードは、メモリ上で次の5つのフィールドによって表現されます。

• 親ポインタ（parent）： 親ノードのアドレスを格納します。これにより、各ノードが二項ヒープ構造の中で正しく連結されます。

• キー（key）： ノードが保持するデータ（キー値）を格納します。

• 次数（degree）： そのノードの次数（子の数＝木のレベル）を示します。

• 左子ポインタ（child）： 直下の最も左の子ノードのアドレスを格納し、該当する場合に子ノードと連結します。

• 兄弟ポインタ（sibling）： 直近の右の兄弟ノードのアドレスを格納します。

このノード構造は、C++では以下のように定義できます。

struct BinomialNode {
    int key;               // キー（データ）
    int degree;            // 次数
    BinomialNode* parent;  // 親へのポインタ
    BinomialNode* child;   // 最も左の子へのポインタ
    BinomialNode* sibling; // 右の兄弟へのポインタ
};

具体例

1. 単一ノードのメモリ表現

単独のノードの場合、親・子・兄弟のいずれのポインタも NULL を指し、キーと次数のみが有効な値を持ちます。

2. 親ノードと子ノードのメモリ表現

親ノードの child ポインタは子ノードを参照し、逆に子ノードの parent ポインタは親ノードを参照することで、双方向の連結が実現されます。

3. 兄弟ノードのメモリ表現

兄弟同士は sibling ポインタで連結されており、これにより同一の親を持つ子ノード群を連結リストとして順番に辿ることができます。