Meldable DEPQ (MDEPQ)
MDEPQ = DEPQ (Double-Ended Priority Queue) ที่เพิ่ม Operation: meld(p, q) = ผสาน DEPQs p และ q → Single DEPQ ที่มี Elements ทั้งหมดของ p และ q
Meld = Destructive (p และ q ไม่เหลือเป็น Independent DEPQs)
Complexity Results
| Structure | Meld Complexity | หมายเหตุ |
|---|---|---|
| Min-Max Pair Heap (Explicit Pointers) | O(log(n/k) · log k) (k ≤ n) | ต้องใช้ Explicit Pointers (ไม่ใช่ Array) |
| Min-Max Heaps | Ω(a + b) (a, b = Sizes) | Linear Time Required |
| MDEPQ (O(1) Min/Max/Insert/Meld) | O(1) Meld, Insert, Min, Max | Delete Min/Max = O(log n) |
| Leftist Trees Adaptation | O(log n) Meld | Operations อื่นๆ เท่า DEPQ Structures อื่นๆ |
| FMPQ-based Total Correspondence | O(1) Meld, Insert, Min, Max | RemoveMin/RemoveMax = O(log n), Space ≈ Half of Dual PQ |
Key Insights
- Meld < Linear Time → ต้องใช้ Explicit Pointers (Pointer-based, ไม่ใช่ Array-based)
- Leftist Trees → Simple MDEPQ Representation, Logarithmic Meld
- FMPQ (Fast Meldable PQ) Base → Total Correspondence MDEPQ: RemoveMin/Max = Log, Others = Constant, Space Efficient
- Total Correspondence > Dual PQ Adaptation (Speed + Space)
สรุป
Meldable DEPQs รองรับ Meld Operation ได้อย่างมีประสิทธิภาพ
Best Structures: Leftist Trees (Simple, Log Meld), FMPQ-based (Fast, Space Efficient)
Trade-off: Meld Speed vs Other Operations vs Space
