データ構造入門：二項ヒープ（Binomial Heap）の基礎と性質を徹底解説

二項ヒープ（Binomial Heap）は、複数の「二項木（Binomial Tree）」を集めて構成されるデータ構造です。二項木 B_k は再帰的に定義される順序付き木であり、最も単純な二項木 B₀ は、たった1つのノードから成ります。

二項木の定義

二項木 B_k は、2つの二項木 B_k-1 を連結することで構成されます。このとき、一方の木の根が、もう一方の木の根の最も左の子となります。この定義により、木の規模は段階的に倍々に増えていくという特徴的な構造を持っています。

いくつかの二項ヒープの例を以下に示します。

二項木の主な性質

• 二項木 B_k は、ちょうど 2^k 個のノードを持ちます。
• 木の高さは k になります。
• 深さ i（0 ≤ i ≤ k）には、正確に $$\left(\begin{array}{c}k\\ j\end{array}\right)$$ 個のノードが存在します。これは二項係数に一致することから、「二項木」という名前の由来にもなっています。

二項ヒープとは

二項ヒープ H は、二項木の集合として定義され、次の2つの重要な性質を満たします。

• ヒープ順序の保持：H に含まれる各二項木はヒープ順序に従います。つまり、任意のノードのキー値は、その親ノードのキー値以上になります。
• 次数の一意性：同じ次数を持つ根をもつ二項木は、H の中に高々1つしか存在しません。

二項ヒープの具体例

上図の二項ヒープ H は、二項木 B₀、B₂、B₃ から構成されています。それぞれのノード数は 1個、4個、8個であり、合計で n = 13 個のノードを持ちます。これらの二項木の根同士は、次数が小さい順に並んだ連結リストによってリンクされています。

このような構造を採用することで、二項ヒープは挿入・統合（マージ）・最小要素の削除などの操作を効率的に実行できます。特に、2つのヒープを高速に統合できる点が通常の二分ヒープに対する大きな強みであり、優先度付きキューの実装などに広く活用されています。