---
# System prepended metadata

title: Symmetric Min-Max Heap
tags: [Data Structure]

---

---
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 (右兄弟)
>   

```graphviz
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 (右兄弟)

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

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

```graphviz
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 )

```graphviz
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

```graphviz
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$ 成立

```graphviz
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$ 不成立

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

* 交換

```graphviz
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 )

```graphviz
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 成立

```graphviz
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 定義，交換

```graphviz
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 定義，交換


```graphviz
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 即可
```graphviz
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

```graphviz
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 成立

```graphviz
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 中最小值


```graphviz
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 成立
```graphviz
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 中最小值
```graphviz
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 結束
```graphviz
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`