Interval Heap = Double-Ended Priority Queue (DEPQ)
Operations และ Complexity:
| Operation | Description | Time Complexity |
|---|---|---|
| isEmpty() | Check if DEPQ Empty | O(1) |
| size() | Return Total Elements | O(1) |
| getMin() | Return Lowest Priority Element | O(1) |
| getMax() | Return Highest Priority Element | O(1) |
| put(z) | Insert Element z | O(log n) |
| removeMin() | Remove & Return Smallest Priority | O(log n) |
| removeMax() | Remove & Return Highest Priority | O(log n) |
Initialization
Initialize n-element Interval Heap: O(n) Time
Interval Heap Structure
- Complete Binary Tree, แต่ละ Node มี 2 Elements
- Left Element ≤ Right Element (Closed Interval [a, b])
- Node Intervals ⊆ Parent Interval (Sub-intervals)
- Left Elements = Min Heap, Right Elements = Max Heap
Even/Odd Cases
- Even Elements: ทุก Node มี 2 Elements [a, b], a ≤ b
- Odd Elements: Last Node มี 1 Element [a] (หรือ [a, a])
