ランダム化された融合可能なヒープ

メルト（マージとも呼ばれる）操作の基本的な目的は、2つのヒープ（それぞれのルートノードQ1とQ2）をマージし、結果として単一のヒープノードを返すことです。このヒープノードは、Q1とQ2をルートとする2つのサブツリーのすべての要素を含むヒープのルートノードとなります。

このマージ操作の優れた特徴は、再帰的に定義できることです。どちらかのヒープが null の場合、マージは空のセットで行われ、メソッドは単に空でないヒープのルート ノードを返します。Q1 と Q2 の両方が nil でない場合、Q1 > Q2 かどうかを確認します。そうであれば、2 つを交換します。したがって、Q1 < Q2 であり、マージされたヒープのルート ノードに Q1 が含まれることが保証されます。次に、Q2 を Q1.left または Q1.right と再帰的にマージします。このステップでランダム化が行われます。マージする側を決定するのはコイン投げです。

function Meld( Node Q 1, Node Q 2) if Q 1 is nil => return Q 2 if Q 2 is nil => return Q 1 if Q1 > Q 2 => swap Q 1 and Q 2 if coin_toss is 0 => Q 1. left = Meld( Q 1. left , Q 2) else Q 1. right = Meld( Q 1. right , Q 2) return Q 1

結合操作が完了したら、結合可能なヒープへの挿入は簡単です。まず、値 x を含む新しいノード u を作成します。次に、この新しいノードをヒープのルートノードと結合します。

function Insert(x) Node u = new Node ux = x root = Meld(u, root) root.parent = nil ノード数を増やす

挿入操作と同様に簡単に、Remove() は Meld 操作を使用してルートノードをヒープから削除します。これは、ルートノードの 2 つの子を単純に結合し、返されたノードを新しいルートにすることで行われます。

関数Remove() root = Meld(root.left, root.right) root が nil でない場合=> root.parent = nil ノード数を減らす

ランダム化されたメルダブルヒープにおいておそらく最も簡単な操作である FindMin() は、ヒープのルートノードに現在格納されている要素を単純に返します。

メルダブルヒープに対して実装可能な追加操作で、最悪の場合の効率がO (log n )となるものには、以下のようなものがあります。

• Remove(u) - ノード u とそのキーをヒープから削除します。
• Absorb(Q) - 融合可能なヒープ Q のすべての要素をこのヒープに追加し、その過程で Q を空にします。
• DecreaseKey(u, y) - ノード u のキーを y に減らします (前提条件: y ≤ ux)。