Dual Heap (โครงสร้างคู่)
General Methods: สร้าง DEPQ จาก Single-ended PQ ที่มี remove(node) Operation
Dual Structure: Min PQ + Max PQ + Correspondence Pointers (Same Element)
Figure A: Dual Heap (7,8,3,6,5) Red Arrows = Correspondence Pointers
Note: เก็บ Element ในหนึ่ง Heap พอ (Figure แสดงทั้งคู่เพื่อความเข้าใจ)
Operations
- isEmpty(), size(): Variable size
- getMin(): Min Heap Root, getMax(): Max Heap Root
- Insert A: Insert ใน Min + Max Heaps → Setup Correspondence
- RemoveMin: removeMin(Min Heap) + remove(aNode) จาก Max Heap (aNode = Corresponding)
- RemoveMax: removeMax(Max Heap) + remove(aNode) จาก Min Heap
Total and Leaf Correspondence
Sophisticated Techniques: Half Elements ใน Min PQ, Half ใน Max PQ, Odd → Buffer
Total Correspondence
x ∈ Min PQ ↔ Distinct y ∈ Max PQ, priority(x) ≤ priority(y)
Figure B: Total Correspondence Heap (11 Elements, Buffer=10)
Leaf Correspondence
Leaf Elements ของ Min/Max PQ = Corresponding Pairs, Non-leaf = No Pair Required
Figure C: Leaf Correspondence Heap
Comparison และ Supported Base Structures
| Technique | Space | Algo Complexity | Speed |
|---|---|---|---|
| Dual | Highest | Simplest | Baseline |
| Total Correspondence | Lower | Complex | Medium |
| Leaf Correspondence | Lower | Most Complex | Fastest |
Base Structures: Heaps, Height-Biased Leftist Trees, Pairing Heaps
put(x), removeMin(), removeMax() = O(log n) (Pairing = Amortized)
Other DEPQ Ops = O(1)
