คิวอันดับที่รวมได้ (Meldable Priority Queues)
นิยาม
Randomized Meldable Heap (หรือ Meldable Heap, Randomized Meldable Priority Queue) เป็นโครงสร้างข้อมูลแบบคิวอันดับ ที่โครงสร้างพื้นฐานคือ Binary Tree ที่จัดลำดับแบบฮีป (Heap-ordered Binary Tree) แต่ไม่มีกติกาแข็งขาดเกี่ยวกับรูปร่างของ Binary Tree
ข้อดี
- วิธีการที่ เรียบง่ายกว่า โครงสร้างข้อมูลอื่นๆ
- การดำเนินการทั้งหมด นำไปใช้ได้ง่าย และค่าคงที่ในขีดจำกัดความซับซ้อนมีค่าน้อย
- ไม่ต้องรักษาเงื่อนไขสมดุล (Balance Conditions) และไม่ต้องมีข้อมูลดาวเทียม (Satellite Information) ในโหนด
- แสดง ประสิทธิภาพเวลา worst-case ที่ดี – การดำเนินการแต่ละครั้งใช้เวลา logarithmic ด้วยความน่าจะเป็นสูง
สกิวฮีป (Skew Heaps)
Skew Heap (หรือ Self-Adjusting Heap) เป็นโครงสร้างข้อมูลฮีปที่นำไปใช้เป็น Binary Tree
ข้อดี
สามารถ รวม (Merge) ได้เร็วกว่า Binary Heaps
เงื่อนไขเพียงสองข้อ
- ต้องรักษา Heap Order ทั่วไป (Root เป็นค่าต่ำสุด และเป็นจริงแบบเรียกซ้ำสำหรับซับทรี) แต่ ไม่ต้องการคุณสมบัติสมดุล (ทุกระดับต้องเต็มยกเว้นระดับสุดท้าย)
- การดำเนินการหลักคือ Merge เท่านั้น – การดำเนินการอื่นๆ เช่น insert, extractMin สามารถนำไปใช้ได้ผ่าน Merge เพียงอย่างเดียว
ตัวอย่างการ Merge
ให้ Skew Heap 1 เป็น:
Heap ที่สอง:
ผลลัพธ์หลัง Merge:
กระบวนการ Merge แบบเรียกซ้ำ (Recursive Merge)
merge(a1, a2) ให้ a1, a2 เป็น Min Skew Heaps สองตัวที่จะรวม ให้รูทของ a1 น้อยกว่ารูทของ a2 (ถ้าไม่ ให้สลับ) สลับ a1->left และ a1->right a1->left = merge(a2, a1->left)
