メルダブル優先キュー操作

ランダム化されたメルダブルヒープ（メルダブルプライオリティキューとも呼ばれます）は、多くの一般的な操作をサポートします。これらは、挿入、削除、および検索操作、findMinとして知られています。挿入および削除操作は、メルダブルヒープMeld（A1、A2）に固有の追加操作の観点から実装されます。

メルド

meld（マージとも呼ばれる）操作の基本的なターゲットは、A1とA2の2つのヒープ（各ヒープのルートノードを取得することによる）を取得し、それらをマージして、結果として単一のヒープノードを返すことです。このヒープノードは、A1とA2をルートとする2つのサブツリーのすべての要素を含むヒープのルートノードです。

このメルド操作の優れた機能は、再帰的に定義できることです。いずれかのヒープがnull値に関連付けられている場合、マージは空のセットで実行され、メソッドは空でないヒープのルートノードを返します。 A1とA2の両方がnilでない場合は、A1>A2かどうかを確認してください。そうである場合は、2つを交換します。したがって、A1

function Meld(Node A1, Node A2)
if A1 is nil => return A2
if A2 is nil => return A1
if A1 > A2 => swap A1 and A2
if coin_toss is 0 => A1.left = Meld(A1.left, A2)
else A1.right = Meld(A1.right, A2)
return A1

挿入

融合操作が完了すると、融合可能なヒープへの挿入は非常に簡単になります。最初に、値pを含む新しいノードaが作成されます。この新しいノードは、ヒープルートノードと単純にマージされます。

function Insert(p)
Node a = new Node
a.p = p
root = Meld(a, root)
root.parent = nil
increment node count

削除

挿入操作が簡単なのと同じように、Remove（）はMeld操作を実装して、ヒープからルートノードを削除します。これは、ルートノードの2つの子をマージし、返されたノードを新しいルートにするだけで実現されます。

function Remove()
rootNode = Meld(rootNode.left, rootNode.right)
if rootNode is not nil => rootNode.parent = nil
decrement node count

FindMin

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

追加の操作

O（logn）の最悪の場合の効率も持つメルダブルヒープに適用できるいくつかの追加の操作は-

• Remove（a）-ノードaとそのキーをヒープから削除します。
• Absorb（P）-融合可能なヒープPのすべての要素をこのヒープに合計し、プロセスでPを空にします。
• DecreaseKey（a、q）-ノードaのキーをqに減らします（前提条件：q <=a.p）。