Initializing an Interval Heap (การเริ่มต้นอินเตอร์วอลฮีป)

Interval Heap Definition

Interval Heap = Embedded Min-Max Heap ที่แต่ละ Node มี 2 Elements
Complete Binary Tree ที่:

• Left Element ≤ Right Element
• Both Elements Define Closed Interval
• Node Interval (≠ Root) = Sub-interval ของ Parent Node
• Left Elements = Min Heap, Right Elements = Max Heap

Initialization Strategy

คล้าย Ordinary Heap Initialization: Bottom-Up เข้า Root
แต่ละ Subtree: Ensure เป็น Interval Heap

1. Order Elements ใน Root (Left ≤ Right)
2. Reinsert Left Endpoint ของ Subtree Root ใช้ Strategy ของ removeMin
3. Reinsert Right Endpoint ของ Subtree Root ใช้ Strategy ของ removeMax

Even vs Odd Elements

• Even: ทุก Node มี 2 Elements [a, b], a ≤ b
• Odd: Node สุดท้ายมี 1 Element [a] (หรือ [a, a])

สรุป

Interval Heap Initialization = Bottom-Up Construction
แต่ละ Subtree: Fix Root Interval → Reinsert Endpoints ใช้ Min/Max Heap Strategies