---
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**

graph graphname{
1[label=""]
x[label="x = 5" shape=s style=dashed]
}

* 將 Data 存至 Root 後即可

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

**Case 2：含飴弄孫 - Root 有 Grandchild**
* 請想想，這裡使用到 Grandchild 原因為何

> [color=#34d2db]**在定義中有提到：**
>此樹就是由 Min Heap 與 Max Heap 互相交疊形成

<br><br>

* 所以當我們從某 Max/Min Level Node 往 Grandchild 的級距 (也就是 index * 2) 持續下去，相當於在搜尋一顆 Max/Min Heap


<br><br><br>

* 當然這兩顆 "分裂" 出來的 Tree 不完全稱得上是一顆完整的 Max/Min Heap
但是它仍然保留了 Max/Min Heap 最重要的特性，就是 Parent 與 Child 的關係

* 千萬別忘了 Parent 與 Child 的關係是這樣
<br><br><br>

* 回過頭，我們從 Min-Max Heap 移除了 Root Data
<br><br><br>

* 那麼第二小的 Data 莫過於在下一層裡的其中一個 Node

<br><br><br>

* 而我們把這個 Level 放回去 Min-Max Heap 來觀察，不就是 Root 的 Grandchild！

所以我們將 "優先" 搜尋 Root 的 Grandchild

---

* 使用以下 Tree 演示

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

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

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

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

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

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 定義

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 符合定義了
但切記 <font color=red> Min Level 是與 Max Level 互相交疊的</font>，所以還是需要考慮到另一個 Level 的 Parent 與新 Node 之間的關係

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
}

* 舉例說明，刪除一次

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

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

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)

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
}

* 不符合定義，進行交換

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 又有兒子則繼續操作
<br><br><br>

---

**Case 3：含飴弄不到孫 - Root 無合適 Grandchild**
* 考慮以下情況，進行刪除

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 是符合定義的，不須更動

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 已經換人了)

graph graphname{
    
    1 [label="10"]
    2 [label="100"]
    3 [label="2 (嘿嘿)" color=blue]
    4 [label="90"]
    
    1--2
    1--3
    2--4

}

* 所以當沒有與 Grandchild 互動時，還是要記得檢查 Child

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
<br><br>
* 填上編號觀看很容易，但在程式裡若要比較兩 Index ，這兩個對稱的 Index 相對於整棵 Tree 來說彼此有甚麼關係

<br><br>
* **Def：樹起始 Level 1**
我們知道每層的 Level Node 最大值 = $2^{k-1} , k = Level$

<br><br><br>
* 想像每一層 Level Nodes 都是上一層 Level Nodes 數量 "複製" 兩次而來

<br><br><br>
* 上一層的數量若為 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) 刪除，

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

    
}

<br>

#### Minimal Deletion - 最小刪除
* 依照 Min - Heap Deletion 的步驟，將 Root 值 替換成 Last Node 值、並刪除 Last Node

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 的關係

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

}

*

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`