---
title: 'Heap'
disqus: hackmd
---
[TOC]
## Heap Tree - 堆積樹
* $Heap$ 是一顆 $Complete\ Binay\ Tree$
* 最適合當作 $Piority\ Queue$
* 所有 $Parent$ 皆 $\geq$ 或 $\leq$ $Child$
* $Root$ 具有最 大/小 值
* $Insertion$：
1. 依順序放置 $Node$
2. 若不符合與 $Parent$ 定義
3. 向上與 $Parent$ 交換直到 $Root$
* $Deleteion：$
1. 刪除 $Root\ Data$
2. 將 $Last\ Node\ Data$ 置入 $Root$ 並移除 $Last\ Node$
3. 若不符合與 $Child$ 定義則向下交換直到 $Leaf$
* $Max Heap$ ： 將最大的 Child 向上移動
* $Min Heap$ ：將最小的 Child 向上移動
---
### Max Heap - 最大堆積
* Parent >= Child
* Root 最大
```graphviz
digraph graphname{
1 [label="100"]
2 [label="19"]
3 [label="36"]
4 [label="17"]
5 [label="3"]
6 [label="25"]
7 [label="1"]
8 [label="2"]
9 [label="7"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
---
#### **Max Heap Insertion - 插入**
1. 根據 Complete Binary Tree 特性，依序新增節點 5
```graphviz
digraph graphname{
1 [label="100"]
2 [label="19"]
3 [label="36"]
4 [label="17"]
5 [label="3"]
6 [label="25"]
7 [label="1"]
8 [label="2"]
9 [label="7"]
10 [label="5" color=red]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
5->10
}
```
2. Parent 3 < Child 5 ( 不符合 Parent >= Child ) 進行交換
```graphviz
digraph graphname{
1 [label="100"]
2 [label="19"]
3 [label="36"]
4 [label="17"]
5 [label="5" color=red]
6 [label="25"]
7 [label="1"]
8 [label="2"]
9 [label="7"]
10 [label="3"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
5->10
}
```
3. Child Null 結束
:::warning
**Time Complexity ：**
$Worst\ case$ 為從 $Leaf$ 移動到 $Root = Height = \left \lceil log_2(n+1) \right \rceil ≒ O( log_2n )$
:::
---
#### **Max Heap Deleteion - 刪除**
1. 承上例，將 Root Data 移除，並置入 Last Node Data 3，再移除 Last Node
```graphviz
digraph graphname{
1 [label="3" color=red]
2 [label="19"]
3 [label="36"]
4 [label="17"]
5 [label="5"]
6 [label="25"]
7 [label="1"]
8 [label="2"]
9 [label="7"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
2. 判斷他的左兒子：Parent 3 < Child 19 ( 不符合 Parent >= Child )
3. 判斷 Child：19 < 36 ， 比較大的 36 與 3 交換
```graphviz
digraph graphname{
1 [label="36"]
2 [label="19"]
3 [label="3" color=red]
4 [label="17"]
5 [label="5"]
6 [label="25"]
7 [label="1"]
8 [label="2"]
9 [label="7"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
4. Parent 3 < Child 25 ( 不符合 Parent >= Child )
5. 25 與 3 交換
```graphviz
digraph graphname{
1 [label="36"]
2 [label="19"]
3 [label="25"]
4 [label="17"]
5 [label="5"]
6 [label="3" color=red]
7 [label="1"]
8 [label="2"]
9 [label="7"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
6. Child Null 結束
:::warning
**Time Complexity：**
$Worst\ case$ 為從 $Leaf$ 移動到 $Root = Height = \left \lceil log_2(n+1) \right \rceil ≒ O( log_2n )$
因為每一次的判斷非大即小，相當於不停將可能的值乘上 $\frac{1}{2}$
因此不論向上、向下的結果都是一樣的
:::
---
### Min Heap - 最小堆積
* Parent <= Child
* Root 最小
```graphviz
digraph graphname{
1 [label="1"]
2 [label="2"]
3 [label="3"]
4 [label="17"]
5 [label="19"]
6 [label="36"]
7 [label="7"]
8 [label="25"]
9 [label="100"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
---
#### **Min Heap Insert - 插入**
1. 根據 Complete Binary Tree 特性，依序新增節點 5
```graphviz
digraph graphname{
1 [label="1"]
2 [label="2"]
3 [label="3"]
4 [label="17"]
5 [label="19"]
6 [label="36"]
7 [label="7"]
8 [label="25"]
9 [label="100"]
10 [label="5" color=red]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
5->10
}
```
2.Parent 19 > Child 5 ( 不符合 Parent <= Child ) 進行交換
```graphviz
digraph graphname{
1 [label="1"]
2 [label="2"]
3 [label="3"]
4 [label="17"]
5 [label="5" color=red]
6 [label="36"]
7 [label="7"]
8 [label="25"]
9 [label="100"]
10 [label="19"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
5->10
}
```
3.Parent 2 < Child 5 ( 符合 Parent <= Child )
4.結束
:::warning
**Time Complexity：** 同 $Max\ Heap = O(log_2n)$
:::
---
#### **Min Heap Delete - 刪除**
1. 承上例，將 Root 移除，置入 Last Node 19
```graphviz
digraph graphname{
1 [label="19" color=red]
2 [label="2"]
3 [label="3"]
4 [label="17"]
5 [label="5"]
6 [label="36"]
7 [label="7"]
8 [label="25"]
9 [label="100"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
2. Parent 19 > Child ( 不符合 Parent <= Child )
3. 判斷 Child：2 < 3 ， 19 與 2 交換
```graphviz
digraph graphname{
1 [label="2"]
2 [label="19" color=red]
3 [label="3"]
4 [label="17"]
5 [label="5"]
6 [label="36"]
7 [label="7"]
8 [label="25"]
9 [label="100"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
4. Parent 19 > Child ( 不符合 Parent <= Child )
5. 判斷 Child：5 < 17 ， 19 與 5 交換
```graphviz
digraph graphname{
1 [label="2"]
2 [label="5"]
3 [label="3"]
4 [label="17"]
5 [label="19" color=red]
6 [label="36"]
7 [label="7"]
8 [label="25"]
9 [label="100"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
6. Child Null 結束
:::warning
**Time Complexity：** 同 $Max\ Heap = O(log_2n)$
:::
---
### Build Heap - 建置堆積
> [color=#52d356]**Top Down - 由上而下**
> 1. 依序使用 $Insertion$ 從 Root (Top) 進行建置
> 2. 因為 $Insertion$ 中會保持 Heap 性質，所以不需要進行調整
* 給定一筆資料：`2 ,5 ,8 ,3 ,4 ,7 ,1 ,9 ,12` 建立 Max Heap
1. Node 為 Null , Insert 2
```graphviz
digraph graphname{
1 [label="2" color=red]
}
```
2. Insert 5
```graphviz
digraph graphname{
1 [label="2"]
2 [label="5" color=red]
1->2
}
```
3. Parent 2 < Child 5 ( 不符合 Parent >= Child )
4. 交換
```graphviz
digraph graphname{
1 [label="5" color=red]
2 [label="2"]
1->2
}
```
5. Insert 8
```graphviz
digraph graphname{
1 [label="5" ]
2 [label="2"]
3 [label="8"color=red]
1->2
1->3
}
```
6. Parent 5 < Child 8 ( 不符合 Parent >= Child )
7. 交換
```graphviz
digraph graphname{
1 [label="8" color=red]
2 [label="2"]
3 [label="5"]
1->2
1->3
}
```
8. 以此類推
```graphviz
digraph graphname{
1 [label="12"]
2 [label="9"]
3 [label="7"]
4 [label="8"]
5 [label="3"]
6 [label="5"]
7 [label="1"]
8 [label="2"]
9 [label="4" color=red]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
:::warning
**Time Complexity：**
$Insert\ 1$ 個 Node 所需時間為 $O(log_2^n)$
$Insert\ n$ 個 Node 所需時間為 $log_21 + log_22 + ... + log_2n ≒ O(nlog_2n)$
:::
---
> [color=#52d356]**Bottom Up - 由下而上**
> 1. 先將 n 個 Data 先依序建立成 Complete Binary Tree
> 2. 再依序從 Last Parent 往 Root 方向調整每一顆子樹
* 給定一筆資料：`2 ,5 ,8 ,3 ,4 ,7 ,1 ,9 ,12` 建立 Max Heap
1. 依序將 Data 放進 Binary Tree
( 在程式使用時，此 Tree 為 Input ， 所以在 Time Complexity 中不須計算此步驟)
```graphviz
digraph graphname{
1 [label="2"]
2 [label="5"]
3 [label="8"]
4 [label="3"]
5 [label="4"]
6 [label="7"]
7 [label="1"]
8 [label="9"]
9 [label="12"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
2. Last Parent 為 3 ，我們以 3 作為 Root 進行調整
```graphviz
digraph graphname{
1 [label="2"]
2 [label="5"]
3 [label="8"]
4 [label="3" color=blue fontcolor=red]
5 [label="4"]
6 [label="7"]
7 [label="1"]
8 [label="9" color=blue]
9 [label="12" color=blue]
1->2
1->3
2->4
2->5
3->6
3->7
4->8 [color=blue]
4->9 [color=blue]
}
```
3. Parent 3 < Child (不符合 Parent >= Child)
4. 判斷 Child : 9 < 12 ， 將 3 與 12 交換
```graphviz
digraph graphname{
1 [label="2"]
2 [label="5"]
3 [label="8" ]
4 [label="12" color=blue]
5 [label="4"]
6 [label="7"]
7 [label="1"]
8 [label="9" color=blue]
9 [label="3" color=blue fontcolor=red]
1->2
1->3
2->4
2->5
3->6
3->7
4->8 [color=blue]
4->9 [color=blue]
}
```
5. 下一個 Last Parent 為 8 ，我們以 8 作為 Root 進行調整
```graphviz
digraph graphname{
1 [label="2"]
2 [label="5"]
3 [label="8" color=blue fontcolor=red]
4 [label="12"]
5 [label="4"]
6 [label="7" color=blue]
7 [label="1" color=blue]
8 [label="9"]
9 [label="3"]
1->2
1->3
2->4
2->5
3->6 [color=blue]
3->7 [color=blue]
4->8
4->9
}
```
6. Parent 8 >= Child (符合定義)
7. 下一個 Last Parent 為 5 ，我們以 5 作為 Root 進行調整
```graphviz
digraph graphname{
1 [label="2"]
2 [label="5" color=blue fontcolor=red]
3 [label="8" ]
4 [label="12" color=blue]
5 [label="4" color=blue]
6 [label="7" ]
7 [label="1"]
8 [label="9" color=blue]
9 [label="3" color=blue]
1->2
1->3
2->4 [color=blue]
2->5 [color=blue]
3->6
3->7
4->8 [color=blue]
4->9 [color=blue]
}
```
8. Parent 5 < Child 12 (不符合 Parent >= Child)
9. 進行交換
```graphviz
digraph graphname{
1 [label="2"]
2 [label="12" color=blue ]
3 [label="8" ]
4 [label="5" color=blue fontcolor=red]
5 [label="4" color=blue]
6 [label="7" ]
7 [label="1"]
8 [label="9" color=blue]
9 [label="3" color=blue]
1->2
1->3
2->4 [color=blue]
2->5 [color=blue]
3->6
3->7
4->8 [color=blue]
4->9 [color=blue]
}
```
10. Parent 5 < Child 9 (不符合 Parent >= Child)
11. 進行交換
```graphviz
digraph graphname{
1 [label="2"]
2 [label="12" color=blue ]
3 [label="8" ]
4 [label="9" color=blue ]
5 [label="4" color=blue]
6 [label="7" ]
7 [label="1"]
8 [label="5" color=blue fontcolor=red]
9 [label="3" color=blue]
1->2
1->3
2->4 [color=blue]
2->5 [color=blue]
3->6
3->7
4->8 [color=blue]
4->9 [color=blue]
}
```
12. 下一個 Last Parent 為 2 ，我們以 2 作為 Root 進行調整
```graphviz
digraph graphname{
1 [label="2" color=blue fontcolor=red]
2 [label="12" color=blue ]
3 [label="8" color=blue]
4 [label="9" color=blue ]
5 [label="4" color=blue]
6 [label="7" color=blue]
7 [label="1"color=blue]
8 [label="5" color=blue ]
9 [label="3" color=blue]
1->2 [color=blue]
1->3 [color=blue]
2->4 [color=blue]
2->5 [color=blue]
3->6 [color=blue]
3->7 [color=blue]
4->8 [color=blue]
4->9 [color=blue]
}
```
13. Parent 2 < Child (不符合 Parent >= Child)
14. 判斷 Child : 12 > 8 ， 將 2 與 12 交換
```graphviz
digraph graphname{
1 [label="12" color=blue ]
2 [label="2" color=blue fontcolor=red]
3 [label="8" color=blue]
4 [label="9" color=blue ]
5 [label="4" color=blue]
6 [label="7" color=blue]
7 [label="1"color=blue]
8 [label="5" color=blue ]
9 [label="3" color=blue]
1->2 [color=blue]
1->3 [color=blue]
2->4 [color=blue]
2->5 [color=blue]
3->6 [color=blue]
3->7 [color=blue]
4->8 [color=blue]
4->9 [color=blue]
}
```
14. Parent 2 < Child (不符合 Parent >= Child)
15. 判斷 Child : 9 > 4 ， 將 2 與 9 交換
```graphviz
digraph graphname{
1 [label="12" color=blue ]
2 [label="9" color=blue ]
3 [label="8" color=blue]
4 [label="2" color=blue fontcolor=red]
5 [label="4" color=blue]
6 [label="7" color=blue]
7 [label="1"color=blue]
8 [label="5" color=blue ]
9 [label="3" color=blue]
1->2 [color=blue]
1->3 [color=blue]
2->4 [color=blue]
2->5 [color=blue]
3->6 [color=blue]
3->7 [color=blue]
4->8 [color=blue]
4->9 [color=blue]
}
```
14. Parent 2 < Child (不符合 Parent >= Child)
15. 判斷 Child : 5 > 3 ， 將 2 與 5 交換
```graphviz
digraph graphname{
1 [label="12" color=blue ]
2 [label="9" color=blue ]
3 [label="8" color=blue]
4 [label="5" color=blue ]
5 [label="4" color=blue]
6 [label="7" color=blue]
7 [label="1"color=blue]
8 [label="2" color=blue fontcolor=red]
9 [label="3" color=blue]
1->2 [color=blue]
1->3 [color=blue]
2->4 [color=blue]
2->5 [color=blue]
3->6 [color=blue]
3->7 [color=blue]
4->8 [color=blue]
4->9 [color=blue]
}
```
16.無 Next Last Parent 結束
```graphviz
digraph graphname{
1 [label="12"]
2 [label="9"]
3 [label="8"]
4 [label="5"]
5 [label="4"]
6 [label="7"]
7 [label="1"]
8 [label="2"]
9 [label="3"]
1->2
1->3
2->4
2->5
3->6
3->7
4->8
4->9
}
```
:::danger
眼尖的同學可能會發現
同樣一筆次序的資料，**Bottom Up** 及 **Top Down** 的結果並不一致
因此我們可以推論 **Heap Binary Tree** 不具唯一性
:::
* 喝個水休息一下，以下我們將花點時間討論 **Bottom Up** 的 **演算法**
藉由此圖初步說明 **[Bottom Up - Analysis Diagram](https://i.imgur.com/fK8A7lu.png)**
:::success
* **Bottom Up 演算法分析**
依照演算法的步驟，我們會先從 Last Parent 開始進行整理
也就是圖中 Level 4 藍色三角形那一列
若藍色三角形裡發生 Parent 與 Child 定義不符合時
我們需要調整的最多步驟為：5 - 4 = 1步，也就是 Leaf (Level 5) 與該 Level 的距離
* 由此可得
1. Level 4 裡其中一個藍色三角形到 Leaf 的移動成本為 1
2. Level 4 裡有 2^4-1^ = 8 個藍色三角形
( 也就是以 Level 4 的 Node 為 Root 的子樹有 8 顆 )
3. 藍色三角形數量 $*$ 藍色三角形最大移動成本 = 藍色三角形移動總成本
4. 也就是圖中的 8 * 1 = 8
<br>
依序還有 綠色、橘色、紅色 三角形需要計算相加
即可得整棵樹的最大移動成本
由此整理出以下數學公式
* **Def：樹高起始點 = 1，樹葉高度 = k，Last Parent Level = i**
1. $\displaystyle\sum_{樹高起點}^{樹葉高度}(該\ Level\ 最多\ Node\ 數*與\ Leaf\ 的距離)$
2. $\displaystyle\sum_{i=1}^{k}(2^{i-1}*(k-i))$ <br>
大家應該有發現紫色三角形，也就是 Last Parent 到了 Leaf 時
因為已經沒有 Child ，所以不管 Leaf 有多少，移動成本皆為 0
代表我們並不用在 [Summation](https://en.wikipedia.org/wiki/Summation) 裡將此納入計算
3. 得 $\displaystyle\sum_{i=1}^{k-1}(2^{i-1}*(k-i))$
要注意的是，在公式裡我們從 Level 1 開始進行計算
是假設過程中的每一步都是最大成本，所以次序並不那麼重要
而在實際操作時必須確實地從 Last Parent 逐漸往上調整
否則將無法做出符合 Max/Min Heap 的 Tree
4. 當然你也可以改變一下 Summation： $\displaystyle\sum_{i=1}^{k-1}(2^{k-i-1}*i)$
:::
:::warning
**Time Complexity：**
為了求出 **Big-O** 我們將 $\displaystyle\sum_{i=1}^{k-1}(2^{i-1}*(k-i))$ 展開、嘗試整理
<br>
* Let $Cost = 2^0*(k-1)+2^1*(k-2)+...+2^{k-3}*(2)+2^{k-2}*(1)$
(以下用點小技巧)
* $2 * Cost = 2^1*(k-1)+2^2*(k-2)+...+2^{k-3}*(3)+2^{k-2}*(2)+2^{k-1}*(1)$
:::
* 我們將 **$(2*Cost) - (Cost)$**
:::warning
* 得 $Cost = -2^0*(k-1)+2^1+2^2+...+2^{k-2}+2^{k-1}$<br>
我們發現了一等比數列：$2^1+2^2+...+2^{k-2}+2^{k-1}$<br>
根據等比級數求和公式：$\dfrac{公比^{最大項次方+1}-首項}{公比-1}$ 得：$\dfrac{2^k-2^1}{2-1}$ = $2^k-2$ <br>
整理 $(2^k-2)-(2^0*(k-1))=2^k-k-1$ :+1: <br>
到此你應該會感到非常興奮，如果沒有的話代表你迷失在處理公式的迷宮裡
回顧一下我們到底在做甚麼事情，以下是我們的初衷
1. Level 4 裡其中一個藍色三角形到 Leaf 的移動成本為 1
2. Level 4 裡有 2^4-1^ = 8 個藍色三角形
( 也就是以 Level 4 的 Node 為 Root 的子樹有 8 顆 )
3. 藍色三角形數量 * 藍色三角形最大移動成本 = 藍色三角形移動總成本
4. 也就是圖中的 8 * 1 = 8
依序還有 綠色、橘色、紅色 三角形需要計算相加
即可得整棵樹的最大移動成本
由此整理出以下數學公式
* 沒錯，我們從好幾串的文字敘述精簡到了 $2^k-k-1$ 這樣的公式
那麼．．． $k$ 是甚麼？ $k$ 是高度你還記得吧！
代表只要將高度代入就可以省去三角形圖的繁瑣計算
圖中的 Level = $5$，代入 $2^k-k-1$<br>
**=> $2^5-5-1$ = 三角形圖裡各層最大成本合 = $4+6+8+8=26$**<br>
這就是 **數學與演算法之美**
於是你可以在自己的函式庫裡新增一個功能就叫做：
int 二元堆積樹的最大成本(int 樹高){
return pow(2,樹高)-樹高-1
}
* 是不是很棒呢，希望可以增加你對數學的熱忱<br>
回歸正題，我們要求出 $2^k-k-1$ 的 **Big-O**<br>
設 $n = 2^k$ , 即 $k=log_2n$<br>
<br>
1. 將 $k=log_2n$ 代入 $2^k-k-1$
3. $2^{log_2n}-log_2n-1$
4. 根據對數性質：$2^{log_2n}$ = $n^{log_22}$
5. $n^{log_22}-log_2n-1$
6. $n-log_2n-1$
7. $n-log_2n-1$ ≦ $c*n=n$ (設$c$為常數=$1$)<br>
<br>
得 **Bottom up 之 Time Complexity ：O(n)**
:::
> [color=#]在經由一連串的分解後我們終於得到了 Bottom Up 的 Time Complexity
>
> 且值得慶幸的是，該 Time Complexity 比 Top Down **O(nlogn)** 的還要快上很多
>
> 所以看似簡單易懂的演算法，不一定會比艱澀難懂的還要快呢！
>
> [time=Tue, May 7, 2019 12:50 AM]
---
### 刪除 插入 建置 Bottom up之調整 Code
To be continued
###### tags: `Data Structure`
Sign in with Wallet
Connect another wallet