二項式ヒープ

2 つのヒープをマージする操作は、他のほとんどの操作のサブルーチンとして使用されます。この手順内の基本的なサブルーチンは、同じ次数の二項ツリーのペアをマージします。これは、2 つのツリーのルートにあるキー (両方のツリーで最小のキー) を比較することによって実行できます。キーが大きい方のルート ノードは、キーが小さい方のルート ノードの子になり、その次数が 1 つ増加します。^{[ 1 ] [ 3 ]}

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

2 つのヒープをより一般的にマージするには、マージ アルゴリズムと同様の方法で、両方のヒープのルートのリストを同時に走査し、ツリーのオーダーが小さいものから大きいものへと順に走査します。マージされる 2 つのヒープのうち一方にのみオーダーのツリーが含まれている場合${\displaystyle j}$この木は出力ヒープに移動されます。2 つのヒープの両方に次数 の木が含まれている場合${\displaystyle j}$2 つのツリーは、次の 1 つのツリーにマージされます。${\displaystyle j+1}$これにより、最小ヒープ特性が満たされます。後々、この木を別の次数を持つ木とマージする必要が生じるかもしれません。${\displaystyle j+1}$2 つの入力ヒープのいずれかに存在します。アルゴリズムの実行中に、最大で 3 つの任意の次数の木を調べます。2 つはマージする 2 つのヒープから、1 つは 2 つのより小さな木から構成されます。^{[ 1 ] [ 3 ]}

function merge(p, q) while not (p.end() and q.end()) tree = mergeTree(p.currentTree(), q.currentTree())

 heap.currentTree().empty()でない場合 tree = mergeTree(tree, heap.currentTree())

 heap.addTree(tree) heap.next(); p.next(); q.next()

二項ヒープ内の各二項木は、そのサイズの二進表現のビットに対応するため、2 つのヒープのマージと、 2 つのヒープのサイズを右から左に二進数で加算することの間には類似性があります。加算中にキャリーが発生すると、これはマージ中に 2 つの二項木がマージされることに対応します。^{[ 1 ] [ 3 ]}

マージ中の各二項木の走査は根のみに関係するため、かかる時間は最大でもオーダーになります${\displaystyle \log _{2}n}$したがって、実行時間は${\displaystyle O(\log n)}$[ ^{1 ] [ 3 ]​}

ヒープに新しい要素を挿入するには、その要素のみを含む新しいヒープを作成し、それを元のヒープとマージするだけで済みます。マージのため、1つの挿入に時間がかかります。${\displaystyle O(\log n)}$しかし、マージされたヒープのうち1つだけがより大きな次数を持つツリーを持つようになった時点でマージをショートカットするマージ手順を使用することで、これを高速化できます。この高速化により、一連の${\displaystyle k}$連続挿入の場合、挿入にかかる合計時間は${\displaystyle O(k+\log n)}$別の言い方をすれば、（シーケンス内の最初の挿入の対数オーバーヘッドの後）各連続挿入の償却時間は${\displaystyle O(1)}$（つまり定数）挿入ごと。^{[ 1 ] [ 3 ]}

二項ヒープの変種であるスキュー二項ヒープは、二進数システムではなくスキュー二進数システムに基づいて木のサイズが決定されたフォレストを使用することで、最悪の場合の挿入時間を一定に保つ。^{[ 4 ]}

ヒープの最小要素を見つけるには、二項ツリーのルートの中で最小値を見つけます。これは次のように実行できます。${\displaystyle O(\log n)}$時間があるだけなので${\displaystyle O(\log n)}$木の根を調べる。^{[ 1 ]}

最小要素を含む二項ツリーへのポインタを使用することで、この操作にかかる時間を短縮できます。${\displaystyle O(1)}$最小値を求める以外の操作を実行する場合は、ポインタを更新する必要があります。これは次のように行うことができます。${\displaystyle O(\log n)}$更新ごとの時間を削減しつつ、いずれの操作の全体的な漸近実行時間も増加させない。

ヒープから最小要素を削除するには、まずその要素を見つけ、二項木のルートから削除し、その子サブツリーのリストを取得します（子サブツリーはそれぞれ異なる次数を持つ二項木です）。このサブツリーのリストを最小の次数から最大の次数に並べ替えて、別の二項ヒープに変換します。次に、このヒープを元のヒープとマージします。各ルートは最大で${\displaystyle \log _{2}n}$子供たちよ、この新しい山を作るには時間がかかる${\displaystyle O(\log n)}$ヒープのマージには時間がかかります${\displaystyle O(\log n)}$そのため、削除操作全体には時間がかかります。${\displaystyle O(\log n)}$[ ^{1 ]​}

function deleteMin(heap) min = heap.trees().first() heap.trees() の各currentについて、 current.root < min.rootの場合はmin = current とし、min.subTrees()の各ツリーについて同様にする。 tmp.addTree(tree) heap.removeTree(min) merge(heap, tmp)

要素のキーを小さくすると、親要素のキーよりも小さくなり、最小ヒープの性質に違反する可能性があります。このような場合は、最小ヒープの性質に違反しなくなるまで、その要素を親要素と交換し、場合によっては祖父母要素とも交換します。各二項木の高さは最大で${\displaystyle \log _{2}n}$なので、これには${\displaystyle O(\log n)}$時間。^{[ 1 ]}ただし、この操作では、ツリーの表現に各ノードからツリー内の親へのポインタを含める必要があり、他の操作の実装がやや複雑になります。^{[ 3 ]}

ヒープから要素を削除するには、そのキーを負の無限大（または同等に、ヒープ内のどの要素よりも小さい値）に減らし、ヒープ内の最小値を削除します。^{[ 1 ]}