Double-Ended Priority Queue (DEPQ)
DEPQ = Data Structure คล้าย Priority Queue/Heap แต่รองรับ Efficient Removal ของทั้ง Max และ Min ตาม Ordering บน Keys/Items
ทุก Element มี Priority/Value ใน DEPQ สามารถ Remove Elements ได้ทั้ง Ascending และ Descending Order
Operations
| Operation | Description |
|---|---|
| isEmpty() | Check if DEPQ Empty → Return True if Empty |
| size() | Return Total Elements in DEPQ |
| getMin(y) | Return Element y with Least Priority |
| getMax(y) | Return Element y with Highest Priority |
| put(y) | Insert Element y into DEPQ |
| removeMin(y) | Remove & Return Element y with Minimum Priority |
| removeMax(y) | Remove & Return Element y with Maximum Priority |
Implementation Methods
1. Balanced BSTs
Min = Leftmost Leaf, Max = Rightmost Leaf
2. Specialized Structures
- Min-Max Heap
- Pairing Heap
- Deap
- Interval Heap
- Symmetric Min-Max Heap (SMMH)
Generic Methods from Normal PQs
Dual Structure Method
Maintain Min PQ + Max PQ + Correspondence Pointers (Same Elements)
Min/Max = Roots of Min/Max Heaps
RemoveMin: removeMin(Min Heap) + remove(node) จาก Max Heap (Corresponding Node)
RemoveMax: removeMax(Max Heap) + remove(node) จาก Min Heap
Total Correspondence
Half Elements in Min PQ, Half in Max PQ, 1-to-1 Correspondence
Odd Count → 1 Element in Buffer
Priority(Min PQ Element) ≤ Priority(Corresponding Max PQ Element)
Leaf Correspondence
Only Leaf Elements of Min/Max PQs Form Corresponding Pairs
Non-leaf Elements = No Correspondence Required
Interval Heaps
Embedded Min-Max Heap: Each Node = 2 Elements [a, b], a ≤ b
Complete Binary Tree:
- Left ≤ Right
- Closed Interval [a, b]
- Node Interval ⊆ Parent Interval
- Left Elements = Min Heap, Right Elements = Max Heap
สรุป
DEPQ = Essential Data Structure สำหรับ Applications ต้องการ Min และ Max ทั้งคู่
หลาย Implementation Options: Dual, Correspondence-based, Embedded (Min-Max, Interval, SMMH)
เลือกตาม: Space, Speed, Simplicity, Meld Support Requirements
