Min-Max Heap Definition
Min-Max Heap = Complete Binary Tree ที่มี Levels สลับกันระหว่าง Min (Even) และ Max (Odd)
- Even Levels: 0, 2, 4, ... = Min Levels
- Odd Levels: 1, 3, 5, ... = Max Levels
- Root = Level 0 (Min Level)
Properties
- Node แต่ละตัวมี Key ใช้สำหรับ Ordering
- Root = Minimum Element ของทั้ง Heap
- Level 1 (Max Level) มี 2 Elements → หนึ่งในสองเป็น Maximum Element
- Node y บน Min Level: y.key = Smallest Key ใน Subtree Rooted at y
- Node y บน Max Level: y.key = Largest Key ใน Subtree Rooted at y
- Min Level Nodes = Min Nodes, Max Level Nodes = Max Nodes
Max-Min Heap (Variant)
Opposite ของ Min-Max Heap: Root = Maximum, Root's Child = Minimum
Operations Complexity
| Operation | Time Complexity |
|---|---|
| Find Min / Find Max | O(1) |
| Insert | O(log n) |
| Delete Min / Delete Max | O(log n) |
| Build Heap | O(n) |
สรุป
Min-Max Heap = Double-Ended Priority Queue Implementation ที่ Simple และ Space-Efficient
Single Array, Implicit Structure (No Pointers)
Alternating Min/Max Levels → Efficient Min และ Max Operations พร้อมกัน
