Insertion Cases
Case 1: Odd Number of Elements
- New Element → Insert ใน Last Node ก่อน
- Compare กับ Previous Node Elements ซ้ำจนกว่า Interval Heap Criteria ถูกต้อง
- ถ้าไม่ผ่าน Criteria → Move จาก Last Node ไป Root จนกว่าจะถูกต้องทั้งหมด
Case 2: Even Number of Elements
- สร้าง Extra Node ใหม่สำหรับ New Element
- Element อยู่ซ้าย Parent Interval → Min Heap
- Element อยู่ขวา Parent Interval → Max Heap
- Compare.Successively Move จาก Last Node → Root จน Criteria ตรง
- ถ้า Element อยู่ใน Parent Interval เอง → Stop ทันที (No Movement)
Time Complexity
ขึ้นกับจำนวน Movements เพื่อ Satisfy Conditions = O(log n)
สรุป
Interval Heap Insertion: Odd → Add to Last Node, Even → New Node
Classify: Left of Parent = Min Heap, Right of Parent = Max Heap, Within = Stop
Bubble Up/Down จนกว่า Interval Heap Properties ทั้งหมด Hold
O(log n) Time
