ランダム化メルダブルヒープ（メルダブル優先キュー）の基本操作を徹底解説

ランダム化メルダブルヒープ（Randomized Meldable Heap、別名：メルダブル優先キュー）は、挿入・削除・探索といった一般的な操作を多数サポートするデータ構造です。具体的には「挿入（Insert）」「削除（Remove）」、そして最小値を取得する「findMin」が代表的な操作として知られています。さらに、挿入と削除の操作は、メルダブルヒープ固有の追加操作である Meld(A1, A2) を基盤として実装されています。

Meld（マージ）

meld（merge、統合とも呼ばれます）操作の基本的な目的は、2つのヒープA1とA2（それぞれのルートノードを受け取る）を統合し、結果として単一のヒープノードを返すことです。このノードは、A1とA2を根とする2つの部分木に含まれるすべての要素を持つヒープのルートノードとなります。

このmeld操作の優れた特徴は、再帰的に定義できる点です。どちらかのヒープがnull値に関連付けられている場合、マージは空集合との結合として完了し、空でない方のヒープのルートノードがそのまま返されます。A1とA2の両方がnilでない場合は、A1 > A2 であるかどうかを確認し、真であれば2つを入れ替えます。これにより A1 < A2 が保証され、統合後のヒープのルートノードには必ずA1が含まれることになります。続いて、A2とA1.leftまたはA1.rightを再帰的にマージします。ここで登場するのが乱択化（ランダム化）です。どちら側の子とマージするかという判断は、コイントスによって決められるためです。

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

Insert（挿入）

meld操作さえ実装されてしまえば、メルダブルヒープへの挿入は非常にシンプルです。まず、値pを格納した新しいノードaを作成します。その後、この新しいノードをヒープのルートノードとマージするだけで完了です。

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

Remove（削除）

挿入操作と同じくらい簡単で、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(log n)の効率を保てる便利な操作が用意されています。

• Remove(a) - 指定されたノードaとそのキーをヒープから削除します。
• Absorb(P) - 別のメルダブルヒープPのすべての要素をこのヒープに移し、その過程でPを空にします。
• DecreaseKey(a, q) - ノードa内のキーをqへ減少させます（前提条件：q <= a.p）。