Symmetric Min-Max Heaps (SMMH) ในโครงสร้างข้อมูล

Symmetric Min-Max Heap (SMMH) Definition

SMMH = Complete Binary Tree ที่:
- Root ว่าง (Empty)
- Node ทุกตัวยกเว้น Root มี Element 1 ตัวอย่างแน่นอน
- Total Nodes = m + 1 (m = Elements)

Properties

ให้ y เป็น Node ใดๆ, elements(y) = Elements ใน Subtree Rooted at y (Exclude y's Own Element)
Assume elements(y) ≠ ∅. y Satisfy:

1. Left Child of y = Minimum Element ใน elements(y)
2. Right Child of y (ถ้ามี) = Maximum Element ใน elements(y)

Example: y = Node with 81, elements(y) = {7, 15, 31, 41}
Left Child = 7 (Min), Right Child = 41 (Max)

Array Representation (Implicit)

SMMH = Complete Binary Tree → Standard Array Mapping
m = 1: Min = Max = Left Child of Root
m > 1: Min = Left Child of Root, Max = Right Child of Root → getMin/getMax = O(1)

Characterization (3 Properties)

SMMH ⇔ Complete Binary Tree (Empty Root, 1 Element/Node) + Properties:

• A1: Node y ที่มี Right Sibling → Element(y) ≤ Element(Right Sibling)
• A2: Node y ที่มี Grandparent → Element(Left Child of Grandparent) ≤ Element(y)
• A3: Node y ที่มี Grandparent → Element(Right Child of Grandparent) ≥ Element(y)

Note: ถ้า A1 True → A2 และ A3 จะ Violate ได้สูงสุด 1 ตัว

Operations

ใช้ A1-A3 → Simple Algorithms สำหรับ Insert/Remove (Adapt จาก Min/Max Heap Algorithms)
Complexity: O(log m)

Insert Example

Insert 3 into SMMH (Figure 1) → Add Node at Position B (Figure 2) → Insert 3 at B → Fix via Properties

สรุป

SMMH = Symmetric Version ของ Min-Max Heap
Root Empty, 1 Element/Node, Min/Max at Root's Children