Removing the Min Element from Interval Heaps (การลบค่าต่ำสุดจากอินเตอร์วอลฮีป)

RemoveMin Procedure

1. Smallest Element = Left Element ของ Root Node → Remove และ Return
2. Fill Vacancy: Remove Element จาก Last Node → Reinsert เข้า Root
3. Compare กับ Left Elements ของ Descending Nodes จนกว่า Interval Heap Conditions ถูกต้องทั้งหมด
4. ถ้า Left Element > Right Element ณ จุดใด → Swap แล้ว Compare ต่อ
5. สุดท้าย Root จะมี Smallest Element อยู่ Left อีกครั้ง

Detailed Cases

• Empty Heap → removeMin Fails
• 1 Element → Return It, Left Empty Heap
• >1 Elements: Return Left Endpoint of Root, Remove It
• Root = Last Node → Done
• Last Node ≠ Root: Remove Left Point p จาก Last Node
  - ถ้า Last Node ว่าง → Remove Node นั้นออกจาก Heap
  - Reinsert p เริ่มจาก Root (Embedded Min Heap)
  - Move Down: Swap p กับ Right Endpoint r ถ้า p > r (Ensure p ≤ r)
  - Reinsert Strategy = Standard Heap Reinsertion

สรุป

Interval Heap RemoveMin = Remove Root Left + Reinsert Last Node Left Endpoint
Maintain: Left ≤ Right per Node, Left Elements = Min Heap, Right = Max Heap
O(log n) Time, Similar to Min Heap Delete + Cross-Heap Adjustment