ภาพรวม
Randomized Meldable Heap (หรือ Meldable Priority Queue) รองรับการดำเนินการทั่วไป ได้แก่ Insertion, Deletion, และ FindMin การแทรกและลบถูกนำไปใช้ในรูปของการดำเนินการเพิ่มเติมที่เฉพาะเจาะจงคือ Meld(A1, A2)
Meld (Merge)
เป้าหมายคือรับสองฮีป (ผ่านรูทโหนด) A1 และ A2 รวมกัน คืนค่าโหนดรูทเดียวเป็นผลลัพธ์ โหนดรูทนี้เป็นรูทของฮีปที่มีทุกองค์ประกอบจากซับทรีสองตัวที่รูทอยู่ที่ A1 และ A2
จุดเด่น: สามารถนิยามได้แบบ Recursive (เรียกซ้ำ)
อัลกอริทึม
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 // ตอนนี้ A1 < A2 รับประกันว่ารูทของฮีปที่รวมจะเป็น A1 if coin_toss is 0 => A1.left = Meld(A1.left, A2) else => A1.right = Meld(A1.right, A2) return A1
การตัดสินใจด้านไหนที่จะ merge นั้นสุ่มด้วยการทอยเหรียญ (Coin Toss) – นี่คือที่มาของ "Randomized"
Insert
เมื่อ Meld พร้อม Insert ก็ง่าย: สร้างโหนดใหม่ a ที่มีค่า p แล้ว merge กับรูทของฮีป
function Insert(p) Node a = new Node a.p = p root = Meld(a, root) root.parent = nil increment node count
Remove
เหมือน Insert ใช้ Meld เพื่อลบรูท: รวมลูกสองตัวของรูท แล้วทำให้โหนดที่คืนมาเป็นรูทใหม่
function Remove() rootNode = Meld(rootNode.left, rootNode.right) if rootNode is not nil => rootNode.parent = nil decrement node count
FindMin
การดำเนินการที่ง่ายที่สุด – คืนค่าองค์ประกอบที่เก็บอยู่ในรูทของฮีป
การดำเนินการเพิ่มเติม (O(log n) worst-case)
- Remove(a) – ลบโหนด a และคีย์ของมันออกจากฮีป
- Absorb(P) – รวมทุกองค์ประกอบของฮีป P เข้ามา ทำให้ P ว่าง
- DecreaseKey(a, q) – ลดคีย์ในโหนด a เป็น q (เงื่อนไข: q ≤ a.p)
