---
title: 'Symmetric Min-Max Heap'
disqus: hackmd
---
[TOC]

## Symmetric Min-Max Heap (SMMH)

> [color=#34d2db] **Def：(此為新版的SMMH)**
> 1. 本身是 Complete Binary Tree
> 2. Root 無 Data
> 3. 任意 Node 之 Left Child Data $\leq$ Right Child Data
> 4. 任意 Node 之
> * Left Subtree (左子樹) 為 Min - Heap
> * Right Subtree (右子樹) 為 Max - Heap
> 5. 任意兄弟關係中 Left sibling (左兄弟) $\leq$ Right sibling (右兄弟)
>

graph graphname{
    
    1 [label=""]
    2 [label="4"]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="6"]
    7 [label="40"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
}

---
### Sibling Adjustment - 調整兄弟節點
* Left sibling (左兄弟) $\leq$ Right sibling (右兄弟)

graph graphname{
    
    1 [label=""]
    1--10
    1--5
}

* 若不符合則交換，Swap(10,5)

graph graphname{
    
    1 [label=""]
    1--5
    1--10
}

---

### Grandparent Adjustment - 調整父子節點

* 以 Node 20 舉例，通常要判斷 Parent 關係時我們只要取 $\lfloor\dfrac{index}{2}\rfloor$ 即可
但是別忘記還要保持 Parent 的兄弟關係，也就是 $\lfloor\dfrac{index}{2}\rfloor+1$ ( 紅Node )

graph graphname{
    5[label="5"]
    10[label="10"  color=red]
    1 [label=""]
    1--5
    1--10
    5--20
}

* 你可以選擇上述的取法，或是直接 $\lfloor\dfrac{index}{4}\rfloor$ 取得 Grandparent 在找他的 Child

graph graphname{
    5[label="5"]
    10[label="10"]
    1 [label=""   color=blue]
    1--5[color=red]
    1--10[color=red]
    5--20
}

* 左邊的 Parent 是 Min-Heap ， $5\le20$ 成立

graph graphname{
    5[label="5" color=blue]
    10[label="10"]
    20[label="20"color=blue]
    1 [label=""]
    1--5
    1--10
    5--20
}

* 右邊的 Parent 是 Max-Heap ， $10\geq20$ 不成立

graph graphname{
    5[label="5" ]
    10[label="10" color=blue]
    20[label="20"color=blue]
    1 [label=""]
    1--5
    1--10
    5--20
}

* 交換

graph graphname{
    5[label="5" ]
    10[label="10"]
    20[label="20" color=blue]
    1 [label=""]
    1--5
    1--20
    5--10
}

---

### Insertion - 插入

* 只要運用上面兩個條件就能實現插入的功能
* 根據 Complete Binary Tree 性質將新 Node 2 放置第 n+1 位置 ( n = nodes )

graph graphname{
    1 [label=""]
    2 [label="4"]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="6"]
    7 [label="40"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="2" color=red]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

* 因為沒有 Sibling 所以直接判斷 Parent：40 > 2 成立

graph graphname{
    1 [label=""]
    2 [label="4"]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="6"]
    7 [label="40"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="2" color=red]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

* 6 > 2 不符合 Min-Heap 定義，交換

graph graphname{
    1 [label=""]
    2 [label="4"]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="2" color=red]
    7 [label="40"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="6"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

* 4 > 2 不符合 Min-Heap 定義，交換

graph graphname{
    1 [label=""]
    2 [label="2" color=red]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="4"]
    7 [label="40"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="6"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

:::warning
**Time Complexity：O(log~n~)**
:::

---

### Deletion - 刪除

* 同一般 Heap 從 Root 刪除，因為 Root 分成 Max/Min - Heap 我們可以選擇

1. Min Deletion ( Left Subtree )
2. Max Deletion ( Right Subtree )
* 因為現在是改變 Parent 所以檢查完 Sibling 之後改成檢查 Grandchild 重複此循環下去直到 Leaf 即可

graph graphname{
    1 [label=""]
    2 [label="2"]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="4"]
    7 [label="50"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="6"]
    15[label="40"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
    7--15
}

* 移除 2

graph graphname{
    1 [label=""]
    2 [label="" color=red]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="4"]
    7 [label="50"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="6"]
    15[label="40"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
    7--15
}

* 將 Last Node 補進去，判斷 Sibling 40 < 80 成立

graph graphname{
    1 [label=""]
    2 [label="40" color=red]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="4"]
    7 [label="50"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="6"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

* 判斷 Grandchild 中最小值

graph graphname{
    1 [label=""]
    2 [label="40" color=red]
    3 [label="80"]
    4 [label="8" color=blue]
    5 [label="60"]
    6 [label="4" color=blue]
    7 [label="50"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="6"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

* 與 4 交換，判斷 Sibling 成立

graph graphname{
    1 [label=""]
    2 [label="4" color=blue]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="40" color=red]
    7 [label="50"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="6"]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

* 判斷 Grandchild 中最小值

graph graphname{
    1 [label=""]
    2 [label="4"]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="40" color=red]
    7 [label="50"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14" color=blue]
    13 [label="30"]
    14 [label="6" color=blue]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

* 與 6 交換，到達 Leaf 結束

graph graphname{
    1 [label=""]
    2 [label="4"]
    3 [label="80"]
    4 [label="8"]
    5 [label="60"]
    6 [label="6" color=blue]
    7 [label="50"]
    8 [label="12"]
    9 [label="20"]
    10 [label="10"]
    11 [label="16"]
    12 [label="14"]
    13 [label="30"]
    14 [label="40" color=red]
    
    1--2
    1--3
    2--4
    2--5
    3--6
    3--7
    4--8
    4--9
    5--10
    5--11
    6--12
    6--13
    7--14
}

#### Min Deletion

* 同上步驟，將 Right 改為 Left 即可

###### tags: `Data Structure`