Dual Structure Method สำหรับ DEPQs
General Method: สร้าง Efficient DEPQ จาก Single-ended PQ ที่รองรับ remove(node) Operation
Simplest: Dual Structure = Maintain Min PQ + Max PQ ของ DEPQ Elements ทั้งหมด
Correspondence Pointers ระหว่าง Nodes ของ Min/Max PQ ที่เป็น Element เดียวกัน
Figure D: Dual Heap (Elements: 7,8,3,6,5) Red Arrows = Correspondence Pointers
Note: รูปแสดง Element ในทั้ง Min/Max Heaps แต่ Actual Implementation: เก็บใน หนึ่ง Heap เพียงอย่างใดอย่างหนึ่ง (Space Saving)
Operations
- isEmpty(), size(): Variable size Track Element Count
- getMin(): Root ของ Min Heap
- getMax(): Root ของ Max Heap
- Insert(x): Insert x ใน Min Heap และ Max Heap → Setup Correspondence Pointers
- RemoveMin(): removeMin() จาก Min Heap + remove(node) จาก Max Heap (node = Corresponding Node)
- RemoveMax(): removeMax() จาก Max Heap + remove(node) จาก Min Heap
ข้อดี/ข้อเสีย
| ข้อดี | ข้อเสีย |
|---|---|
| Simple to Implement | Space: 2n (หรือ n + Pointers) |
| All Operations O(log n) หรือ O(1) | Maintain Correspondence Pointers = Overhead |
| Works with Any PQ (Heaps, Leftist Trees, Pairing Heaps) | ไม่ Space-Optimal |
