---
# System prepended metadata
title: Min-Max Heap
tags: [Data Structure]
---
---
title: 'Min-Max Heap'
disqus: hackmd
---
[TOC]
## Min-Max Heap
> [color=#34d2db] **Def：**
> 1. 是 Complete Binary Tree
> 2. Level 依序由 Min/Max Heap 交互出現
> 3. Root 在 Min Level
> 4. 某 Node x 在 Min Level，代表以 x 為 Root 的 Tree 中，x 是最小值
> (同理 Max Level)
* 此樹就是由 Min Heap 與 Max Heap 互相交疊形成
* 再次提醒，定義 3 有提到 Root 必須為 Min Level 的值
---
### Insertion - 插入
* 依照 Complete Binary Tree 性質，插入 Node 2
* 此時 Node 2 你不知道他是否符合 Min-Max Heap 的定義，所以我們要與他的 Parent Node 1 比較
* 根據定義 3 ，Root = Node 1 = Min Level，相當於此顆 Tree 是 Min Heap
所以當 Node 2 < Node 1 ，則要進行交換
:::danger
根據插入位置的 Parent Level 判斷
:::
* Parent 於 Min Level 使用 Min - Heap 判斷
* Parent 於 Max Level 使用 Max - Heap 判斷
若新節點與父節點符合定義，要再檢查祖先節點
---
### Deletion - 刪除
* 五步驟
* 移除 Root Data ( 也可以想像成對此 Tree 使用 GetData() )
* 將 Last Node Data 存至變數 x
* 移除 Last Node
* 將 x 存至 Root Data
* "判斷" 新 Root 是否符合定義
**判斷方法：** (語法關係，圖若有單個 Child 請自行想像為 Left Child)
**Case 1：孕育新生命 - Root 無 Child**
```graphviz
graph graphname{
1[label=""]
x[label="x = 5" shape=s style=dashed]
}
```
* 將 Data 存至 Root 後即可
```graphviz
graph graphname{
1[label="5"]
}
```
**Case 2：含飴弄孫 - Root 有 Grandchild**
* 請想想，這裡使用到 Grandchild 原因為何
> [color=#34d2db]**在定義中有提到：**
>此樹就是由 Min Heap 與 Max Heap 互相交疊形成
* 所以當我們從某 Max/Min Level Node 往 Grandchild 的級距 (也就是 index * 2) 持續下去，相當於在搜尋一顆 Max/Min Heap
* 當然這兩顆 "分裂" 出來的 Tree 不完全稱得上是一顆完整的 Max/Min Heap
但是它仍然保留了 Max/Min Heap 最重要的特性，就是 Parent 與 Child 的關係
* 千萬別忘了 Parent 與 Child 的關係是這樣
* 回過頭，我們從 Min-Max Heap 移除了 Root Data
* 那麼第二小的 Data 莫過於在下一層裡的其中一個 Node
* 而我們把這個 Level 放回去 Min-Max Heap 來觀察，不就是 Root 的 Grandchild！
所以我們將 "優先" 搜尋 Root 的 Grandchild
---
* 使用以下 Tree 演示
```graphviz
graph graphname{
1 [label="7"]
2 [label="70"]
3 [label="40"]
4 [label="30"]
5 [label="9"]
6 [label="10"]
7 [label="45"]
1--2
1--3
2--4
2--5
3--6
3--7
}
```
* 移除 Root Data：7
```graphviz
graph graphname{
1 [label=""]
2 [label="70"]
3 [label="40"]
4 [label="30"]
5 [label="9"]
6 [label="10"]
7 [label="45"]
1--2
1--3
2--4
2--5
3--6
3--7
}
```
* 儲存 Last Node Data 至 x
```graphviz
graph graphname{
1 [label=""]
2 [label="70"]
3 [label="40"]
4 [label="30"]
5 [label="9"]
6 [label="10"]
7 [label="45"]
45[label="x = 45" shape=s style=dashed]
1--2
1--3
2--4
2--5
3--6
3--7
}
```
* 移除 Last Node
```graphviz
graph graphname{
1 [label=""]
2 [label="70"]
3 [label="40"]
4 [label="30"]
5 [label="9"]
6 [label="10"]
45[label="x = 45" shape=s style=dashed]
1--2
1--3
2--4
2--5
3--6
}
```
* 將 x 放入 Root Data
```graphviz
graph graphname{
1 [label="45"]
2 [label="70"]
3 [label="40"]
4 [label="30"]
5 [label="9"]
6 [label="10"]
1--2
1--3
2--4
2--5
3--6
}
```
* 使用 case 2
```graphviz
graph graphname{
1 [label="45" color=red]
2 [label="70"]
3 [label="40"]
4 [label="30" color=blue]
5 [label="9" color=blue]
6 [label="10" color=blue]
1--2
1--3
2--4
2--5
3--6
}
```
* 交換完成，且符合 Min-Max Heap 定義
```graphviz
graph graphname{
1 [label="9"]
2 [label="70"]
3 [label="40"]
4 [label="30"]
5 [label="45" color=red]
6 [label="10"]
1--2
1--3
2--4
2--5
3--6
}
```
---
:::danger
**if (爸爸可能不知情)**
:::
* 以上述例子來說，更新完 Tree 之後雖然 Min Level 中的 Node 符合定義了
但切記 Min Level 是與 Max Level 互相交疊的，所以還是需要考慮到另一個 Level 的 Parent 與新 Node 之間的關係
```graphviz
graph graphname{
1 [label=""]
2 [label="你還要先問問我" color=blue]
3 [label=""]
4 [label=""]
5 [label="新 Node" color=red]
6 [label=""]
1--2
1--3
2--4
2--5
3--6
}
```
* 舉例說明，刪除一次
```graphviz
graph graphname{
1 [label="7"]
2 [label="100"]
3 [label="500"]
4 [label="50"]
5 [label="90"]
6 [label="300"]
7 [label="400"]
1--2
1--3
2--4
2--5
3--6
3--7
}
```
* 移除 Root Data 並將 Last Node Data 存入 x ，移除 Last Node
```graphviz
graph graphname{
1 [label="400" color=red]
2 [label="100"]
3 [label="500"]
4 [label="50"]
5 [label="90"]
6 [label="300"]
1--2
1--3
2--4
2--5
3--6
}
```
* 搜尋 Grandchild 並替換最小值：50
```graphviz
graph graphname{
1 [label="50"]
2 [label="100"]
3 [label="500"]
4 [label="400" color=red]
5 [label="90"]
6 [label="300"]
1--2
1--3
2--4
2--5
3--6
}
```
* 檢查 Data 100 的 Root (位於 Max Level) 是否符合定義 (Parent 應當 $>$ Child)
```graphviz
graph graphname{
1 [label="50"]
2 [label="100" color=green]
3 [label="500"]
4 [label="400" color=red]
5 [label="90"]
6 [label="300"]
1--2
1--3
2--4
2--5
3--6
}
```
* 不符合定義，進行交換
```graphviz
graph graphname{
1 [label="50"]
2 [label="400" color=red]
3 [label="500"]
4 [label="100" color=green]
5 [label="90"]
6 [label="300"]
1--2
1--3
2--4
2--5
3--6
}
```
* 而如果 100 又有兒子則繼續操作
---
**Case 3：含飴弄不到孫 - Root 無合適 Grandchild**
* 考慮以下情況，進行刪除
```graphviz
graph graphname{
1 [label="1"]
2 [label="100"]
3 [label="2"]
4 [label="90"]
5 [label="10"]
1--2
1--3
2--4
2--5
}
```
* 我們發現 10 的 Grandchild 是符合定義的，不須更動
```graphviz
graph graphname{
1 [label="10"]
2 [label="100"]
3 [label="2"]
4 [label="90" color=red]
1--2
1--3
2--4
}
```
* 但是 10 的 Child 卻不符合定義 (因為 Parent 已經換人了)
```graphviz
graph graphname{
1 [label="10"]
2 [label="100"]
3 [label="2 (嘿嘿)" color=blue]
4 [label="90"]
1--2
1--3
2--4
}
```
* 所以當沒有與 Grandchild 互動時，還是要記得檢查 Child
```graphviz
graph graphname{
1 [label="2" color=blue]
2 [label="100"]
3 [label="10" ]
4 [label="90"]
1--2
1--3
2--4
}
```
> [color=#]其實 Case 2, 3 是差不多的，不論是 Parent 或 Child 更換，都要再去拜訪彼此是否符合定義
:::warning
**Time Complexity：**$O( log_2n )$
:::
---
## Deap
> [color=#d62234] **Def：**
> 1. 本身是 Complete Binary Tree
> 1. Root 不存 Data
> 2. Root 的 Left Subtree (左子樹) 為 Min-Heap
> 3. Root 的 Right Subtree (右子樹) 為 Max-Heap
> 4. 假設兩顆子樹各自的 Node 編號 (Index) 排列方式一樣，
> 則在相同編號下：左子樹的 Data $\leq$ 右子樹的 Data
* 左子樹的 6 號 = 33 $\leq$ 右子樹的 6 號 = 60
* 填上編號觀看很容易，但在程式裡若要比較兩 Index ，這兩個對稱的 Index 相對於整棵 Tree 來說彼此有甚麼關係
* **Def：樹起始 Level 1**
我們知道每層的 Level Node 最大值 = $2^{k-1} , k = Level$
* 想像每一層 Level Nodes 都是上一層 Level Nodes 數量 "複製" 兩次而來
* 上一層的數量若為 1 個單位 (2 個 Nodes)，下一層的數量就是 2 個單位
而左右 Heap 中 Node 彼此的間距就是 1 單位
* 一個單位 = 上一層的最大 Nodes = $2^{k-2}$
* 所以只要將某個 Index ± $2^{k-2}$，就可以找到隔壁相同位置的 Node，( 加往右，減往左 )
* $Tree[4] = 10 \leq Tree[4+2^{3-2}] = Tree[6] = 70$
---
### Insertion - 插入
* 根據 Complete Binary Tree 特性插入至第 n+1 的位置 (n = Nodes)
則插入的 Node 不是在 Min - Heap 就是在 Max - Heap
* 分為兩種 Case
1. 插入 Min-Heap
* 比較對應 Max-Heap 位置的父節點
2. 插入 Max-Heap
* 比較對應 Min-Heap 位置的節點
交換完之後在做 Insertion (Heapify)
---
### Deletion - 刪除
* 我們可以選擇做最小 (綠Node) 或是最大 (紅Node) 刪除，
```graphviz
graph graphname{
1 [label=""]
2 [label="1" color=green]
3 [label="100" color=red]
4 [label="10"]
5 [label="7"]
6 [label="70"]
7 [label="88"]
8 [label="13"]
9 [label="22"]
10 [label="33"]
11 [label="60"]
12 [label="33"]
13 [label="22"]
14 [label="60"]
15 [label="55"]
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
}
```
#### Minimal Deletion - 最小刪除
* 依照 Min - Heap Deletion 的步驟，將 Root 值 替換成 Last Node 值、並刪除 Last Node
```graphviz
graph graphname{
1 [label=""]
2 [label="55" color=green]
3 [label="100"]
4 [label="10"]
5 [label="7"]
6 [label="70"]
7 [label="88"]
8 [label="13"]
9 [label="22"]
10 [label="33"]
11 [label="60"]
12 [label="33"]
13 [label="22"]
14 [label="60"]
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
}
```
* 確認完 Child 關係後，記得要在判斷與右子樹相對位 Node 的關係
```graphviz
graph graphname{
1 [label=""]
2 [label="7"]
3 [label="100"]
4 [label="10"]
5 [label="33"]
6 [label="70"]
7 [label="88"]
8 [label="13"]
9 [label="22"]
10 [label="55" color=green]
11 [label="60"]
12 [label="33" color=red]
13 [label="22"]
14 [label="60"]
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
}
```
*
```graphviz
graph graphname{
1 [label=""]
2 [label="7"]
3 [label="100"]
4 [label="10"]
5 [label="33"]
6 [label="70"]
7 [label="88"]
8 [label="13"]
9 [label="22"]
10 [label="33" ]
11 [label="60"]
12 [label="55" color=green ]
13 [label="22"]
14 [label="60"]
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
}
```
###### tags: `Data Structure`