C ++の二項ヒープ？

二項ヒープは、二分ヒープの拡張として定義され、二分ヒープによって提供される他の操作と一緒に、より高速なマージまたは結合操作を提供します。

二項ヒープは、二項ツリーのコレクションとして扱われます。

二項ツリーとは何ですか？

次数kの二項ツリーは、次数k-1の2つの二項ツリーを取得し、一方を左端の子またはその他として扱うことで構築できます。

次数kの二項ツリーには以下のプロパティがあります。

• BinomialTreeのノード数は正確に2 ^k です。 。

• BinomialTreeの深さはkです。

• 深さiには正確にkCiノードがあります。ここでi=0、1 、。 。 。 、k。

• 次数kの根と根の子は、それ自体が左から右に次数k-1、k-2、..0の二項ツリーとして扱われます。

二項ヒープ-

二項ヒープは、各二項ツリーがMinHeapプロパティに従う一連の二項ツリーとして定義されます。そして、任意の次数を持つと、任意の次数の最大1つのBinomialTreeが存在する可能性があります。

例二項ヒープ-

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

左から右へ2次および3次の二項ツリー

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

m個のノードを持つ二項ヒープの二項ツリーの数は、mのバイナリ表現のセットビットの数に等しくなります。たとえば、mが13であるとすると、m（00001101）のバイナリ表現に3つのセットビットがあり、3つの二項ツリーを示します。また、これらの二項ツリーの次数をセットビットの位置と関連付けることもできます。この関係の助けを借りて、「m」ノードを持つBinomialHeapにO（logm）二項ツリーがあると判断または結論付けることができます

二項ヒープの操作-

union（）はBinomial Heapのメイン操作であり、他のすべての操作は主にこの操作を実装します。 union（）操作は、2つの二項ヒープを1つに結合する役割を果たします。

• insert（h、K）-キー「K」を二項ヒープ「h」に挿入します。最初に、この操作で単一のキー「K」を使用して二項ヒープを作成し、次にhと新しい二項ヒープでユニオンを呼び出すことができます。

• getMin（h）-getMin（）の簡単な方法は、二項ツリーのルートのリストにアクセスして、最小のキーを返すことです。

  このアプリケーションにはO（logm）時間が必要です。最小のキールートへのポインタを維持することで、O（1）に改善できます。

• extractMin（h）-この操作はunion（）も実装します。最初に、getMin（）を呼び出して最小のキーBinomial Treeを計算し、次にノードを削除し、削除された最小ノードのすべてのサブツリーを組み合わせてnewBinomialヒープを作成します。最後に、hでunion（）と、新しく作成された二項ヒープを呼び出します。この操作にはO（logm）時間が必要です。

• delete（h）-バイナリヒープと同じように、最初は削除操作でキーがマイナス無限に縮小され、次にextractMin（）が呼び出されます。

• decreaseKey（h）-decreaseKey（）もバイナリヒープと同じです。最初に、減少キーをその親と比較し、親のキーがそれ以上の場合は、キーを交換して親に対して繰り返します。最後に、親が小さいキーを持つノードに到達するか、ルートノードに到達すると停止します。 decreaseKey（）の時間計算量はO（logm）です。