二項ヒープとは？わかりやすく解説

二項ヒープ（にこうヒープ、binomial heap）とは、計算機科学におけるデータ構造（ヒープ）の1つである。特徴は以下の通り。

二分ヒープとよく似たデータ構造であるが、二項ヒープは2つのヒープを素早くマージする操作をサポートしている。
特殊な木構造を用いることで実現される。
マージ可能な抽象データ型ヒープ（meldableヒープとも呼ばれる）の実装として重要。

二項木

二項ヒープは二項木の集合として実装される（二分ヒープと比較すると、二分ヒープは単一の二分木から構成される）。二項木は再帰的に定義される。

次数 0の二項木は1つのノードをもつ。
次数 k の二項木は一つの根(root)をもち、その子はそれぞれ次数 k-1, k-2, …, 2, 1, 0の二項木の親である。

次数(order) 0から3までの二項木。それぞれの木はより低い次数の二項木の部分木をもつ根を持っている。点線で囲まれているのが部分木である。例えば、次数 3の二項木は次数 2、1、0の二項木(青と緑、赤で別々に強調されている)がつながっている。

次数 k の二項木は $2^{k}$

key 1, 2, …, 13の要素を含む二項木の例。このヒープは次数 0, 2, 3の3つの二項木から構成されている。

実装

二項木たちの根へのランダムアクセスを要求する操作は無いので、二項木たちの根は連結リストに木の次数の昇順に格納できる。

マージ

上で述べたように、最も単純かつ重要な操作は二つの二項ヒープ内で同じ次数の2つの二項木をマージすることである。二項木の構造からそれは簡単にマージできる。木の中では根は最も小さい要素なので、二つのキーを比較することにより、二つの根の小さいほうが最小のキーになるので、それが新しい根になる。そして、もう一方の木はマージ後の木の部分木となる。この操作は二つの二項ヒープを完全にマージする最も基本的なものである。

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

二つの同じ次数を持つ二項木をマージするには、最初にrootノードのkeyを比較する。7>3なので、左の黒い木(rootノードが7のもの)は右の灰色の木(rootノードが3のもの)に部分木として取り付けられる。結果、次数 3の木となる。

二つのヒープをマージする操作は、他のほとんどの操作においてサブルーチンとして使われる。両方のヒープの根のリストは同時に検査される。これはマージアルゴリズムに似ている。もし、次数 jの木を含んでいるヒープが唯一つだけあるならば、その木はマージされたヒープに移動される。もし、2つのヒープが次数 jの木を含んでいるならば、最小ヒープ特性を満足させるために、二つの木はマージされ次数 j+1の一つの木となる。もしかしたらその後、その木はどちらかのヒープ内の次数 j+1の木とマージする必要が発生するかもしれない。このアルゴリズムの実行中、それぞれの次数について多くとも3つの木を試験する必要がある。（マージする二つのヒープからの二つの木と二つのより小さい木から成る一つの木の計3つ）。それぞれの木の次数は最大でlog₂ nであり、それゆえにマージにかかる時間はO(log n)になる。

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()

この図は2つの二項ヒープのマージを示す。これは同じ次数をもつ二項木のマージを繰り返すことにより達成される。もしマージによってできた二項木が2つのヒープのどちらかの二項木と同じ次数であれば、またマージが行われる。

挿入

ヒープに新しい要素を挿入する操作は、単に挿入する要素のみを含んだ新しいヒープを作成しそれを既存のヒープとマージさせるだけで完了する。実行時間はO(log n)かかる。

最小値検索

ヒープの最小要素を見つけるには、ただ二項木たちの根の中で最小のものを見つけるだけでよい。この処理は O(log n)時間内にたやすく完了できる。

最小要素を含む二項木を指すポインタを使うことによって、この操作にかかる時間をO(1)にまで減らすことができる。そのポインタは最小要素検索以外の任意の操作を行うときにおいても必ず更新しなければならない。この操作は、任意の操作を行う時間とは別にO(log n)時間内に完了する。

最小値削除

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

キー値減算

ある要素のキー値を減らした後、そのキーの親よりもキー値が小さくなったならば、最小ヒープの特性に違反してしまう。この場合、その親の要素と交換し、必要ならばさらにその親とも交換し、最小ヒープの特性には違反しなくなるまで続ける。それぞれの二項木の高さは高々log₂ nであり、この処理にはO(log n)の時間かかる。

削除

ヒープからある要素を削除するには、そのキー値を負の無限大へ減算し（あるいは、ヒープ内の任意の要素よりも小さい値へ減算し）、ヒープ内の最小値を削除する。

パフォーマンス

n 個の要素を持つ二項ヒープに対して、以下の全操作の計算量はO(log n)である。

ヒープに新しい要素を挿入する
最小のキーを持つ要素を検索する
ヒープから最小のキーを持つ要素を削除する
指定された要素のキー値を減算する
ヒープから特定の要素を削除する
二つの任意のヒープを一つのヒープにマージする

最小のキーを持つ要素の検索は、最小キーへのポインタを追加し利用することで、O(1)で実行できる。

派生

二項ヒープの派生は、フィボナッチヒープやソフトヒープのような他の似たようなヒープデータ構造を構築するのに用いられている。

外部リンク

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

二項ヒープとは？わかりやすく解説

二項ヒープ

二項木

実装

マージ