Deap Definition
Deap = Data Structure ที่ Root Node ไม่มี Element/Key Value
สร้างตาม Rules:
- Root Node ว่าง (No Element)
- Left Subtree = Min Heap
- Right Subtree = Max Heap
Deap Property (Mathematical Correctness)
ถ้า Left/Right Subtrees ของ Node ใด Non-empty และ Corresponding Nodes = a (Left), b (Right) →
a.KeyValue ≤ b.KeyValue
ทุก Pair ของ Corresponding Nodes ระหว่าง Min/Max Heaps ต้อง Satisfy Property นี้
Operations
- Find Min: Root ของ Left Subtree (b[2]) → O(1)
- Find Max: Root ของ Right Subtree → O(1)
- Insert: O(log n) - ใช้ min_value/max_value หา Corresponding Node
- Delete Min/Max: O(log n) - Percolate Down + Cross-Subtree Adjustment
สรุป
Deap = Double-Ended Heap Using Two Embedded Heaps (Min + Max)
Root Empty, Left=Min Heap, Right=Max Heap
Corresponding Nodes Property: Min Key ≤ Max Key
