二項ヒープ

二項ヒープとは

二項ヒープは、計算機科学におけるデータ構造の一つで、特にマージ操作に優れたヒープです。二分ヒープと似たデータ構造ですが、二項ヒープは複数のヒープを高速にマージする操作をサポートしています。

これは特殊な木構造によって実現され、マージ可能な抽象データ型ヒープ（meldableヒープ）の実装として重要な役割を果たします。

二項木

二項ヒープは、二項木の集合として実装されます。二分ヒープが単一の二分木で構成されるのに対し、二項ヒープは複数の二項木を組み合わせることで構成されます。

二項木は再帰的に定義され、以下の特徴を持ちます。

次数0の二項木は、単一のノードを持ちます。
次数kの二項木は、一つの根を持ち、その子はそれぞれ次数k-1, k-2, ..., 2, 1, 0の二項木の親となります。

次数kの二項木は、2^k個のノードを持ち、高さはkとなります。この構造により、マージ操作が効率的に行えます。

例えば、次数kの二項木を作成するには、次数k-1の2つの二項木TaとTbを用意し、Ta(またはTb)の一番左の子としてTb(またはTa)を追加します。

この特徴が二項ヒープのマージ操作の中核をなし、従来のヒープよりも優れた点です。

二項ヒープの構造

二項ヒープは、以下の2つの性質を満たす二項木の組で実装されます。

1. 各二項木は、最小ヒープの特性に従い、ノードのキーはその親のキーよりも大きいか等しくなっています。
2. 二項木は、各次数について、ただ1つ存在するか、全く存在しないかのいずれかです。

これらの性質により、各二項木の根がその木の中で最小のキーを持つことが保証され、ヒープ全体でも同様のことが言えます。

また、n個の要素を持つ二項ヒープは、最大でもlog(n + 1)個の二項木で構成されます。これは、nの2進数表現における1のビット数に対応します。

例えば、13は2進数で「1101」と表され、2^3 + 2^2 + 2^0と分解できます。したがって、13個の要素を持つ二項ヒープは、次数3、2、0の3つの二項木から構成されます。

実装

二項木の根へのランダムアクセスは不要なため、根は木の次数の昇順で連結リストに格納できます。

マージ

二項ヒープの最も重要な操作は、同じ次数の二項木同士をマージすることです。これは簡単に行うことができ、二つの木の根のキーを比較し、小さい方を新しい根とし、もう一方の木を部分木として追加します。

この操作を繰り返し行うことで、二つの二項ヒープを完全にマージすることができます。


function mergeTree(p, q)
if p.root <= q.root
return p.addSubTree(q)
else
return q.addSubTree(p)


二つのヒープをマージする操作は、他の多くの操作においてサブルーチンとして使われます。両方のヒープの根のリストを同時に検査し、マージアルゴリズムのように処理します。

もし、次数jの木を含んでいるヒープが一つだけなら、その木をマージ後のヒープに移動します。もし、両方のヒープが次数jの木を含んでいるなら、最小ヒープ特性を満足させるために、二つの木をマージし、次数j+1の木を作ります。この操作を繰り返すことで、二つのヒープをマージできます。


function merge(p, q)
while not( p.end() and q.end() )
tree = mergeTree(p.currentTree(), q.currentTree())
if not heap.currentTree().empty()
tree = mergeTree(tree, heap.currentTree())
heap.addTree(tree)
else
heap.addTree(tree)
heap.next() p.next() q.next()

挿入

ヒープに新しい要素を挿入するには、その要素のみを含む新しいヒープを作成し、既存のヒープとマージします。この操作の計算量はO(log n)です。

最小値検索

ヒープの最小要素を見つけるには、二項木の根の中で最小のものを探します。この処理はO(log n)時間で完了します。最小要素を含む二項木を指すポインタを利用することで、O(1)にまで短縮できます。

最小値削除

最小値を削除するには、まず最小要素を検索し、それを含む二項木から削除します。そして、削除した二項木の部分木のリストを大きい順に並べ替え、元のヒープとマージします。

キー値減算

要素のキー値を減算した後、最小ヒープの特性に違反する場合には、親要素と交換し、違反しなくなるまでこの操作を繰り返します。この処理は二項木の高さに比例し、O(log n)時間で完了します。

削除

任意の要素を削除するには、そのキー値を負の無限大に減算し、最小値を削除します。

パフォーマンス

n個の要素を持つ二項ヒープに対する各操作の計算量は、以下の通りです。

挿入: O(log n)
最小値検索: O(log n) (ポインタ使用時はO(1))
最小値削除: O(log n)
キー値減算: O(log n)
削除: O(log n)
マージ: O(log n)

派生

二項ヒープは、フィボナッチヒープやソフトヒープなどのヒープデータ構造の構築に利用されています。

関連項目

ヒープ
フィボナッチヒープ

外部リンク

* ウィキメディア・コモンズには、二項ヒープに関するカテゴリがあります。

もう一度検索