Correspondence Techniques สำหรับ DEPQs
Total และ Leaf Correspondence = Sophisticated Techniques
ครึ่ง Elements ใน Min PQ, อีกครึ่งใน Max PQ
Odd Count → 1 Element ใน Buffer (ไม่ใช่ Member ของ PQ ใดๆ)
Total Correspondence
Element x ใน Min PQ ↔ Distinct Element y ใน Max PQ
(x, y) = Corresponding Pair: priority(x) ≤ priority(y)
Figure E: Total Correspondence Heap (11 Elements: 3,4,5,5,6,6,7,8,9,10,11, Buffer=10)
Leaf Correspondence
Leaf Elements ของ Min/Max PQ ต้องเป็น Corresponding Pairs
Non-leaf Elements = ไม่ต้อง Pair
Figure F: Leaf Correspondence Heap
Comparison
| Technique | Space | Algorithm Complexity | Speed |
|---|---|---|---|
| Dual Structure | Most (2n) | Simple | Baseline |
| Total Correspondence | Less (n + buffer) | More Complex | Medium |
| Leaf Correspondence | Less (n + buffer) | Most Complex | Fastest |
Applicable Base Structures
เขียน DEPQ Structures จาก: Heaps, Height-Biased Leftist Trees, Pairing Heaps
Operations: put(x), removeMin(), removeMax() = O(log n) (Pairing Heaps = Amortized)
Other DEPQ Operations = O(1)
