owned this note
owned this note
Published
Linked with GitHub
---
title: 'Binomial Heap - 二項式堆積'
disqus: hackmd
---
[TOC]
## Binomial Heap - 二項式堆積 (Algo.)
* **Def：**
1. 此堆積是由 Degree 0 的樹依序堆積下去
2. Degree 為 0 的二項樹只有一個 Root
3. Root 下有 $k$ 個 Child，每個 Child ==Degree==分別為 $k-1,k-2,...,2,1,0$
4. 可將二項樹視為 Height 從 0 開始的樹，其 $Nodes = 2^k$ (即為前一棵的 $2$ 倍)
5. 高度或 Degree 為 $k$ 的二項樹，它在 Height 為 h 層 Max Nodes 為 $\left(\begin{array}{ccc}k\\h\end{array}\right)$
6. Degree 為 $k$ 的二項樹可從兩顆 Degree 為 $k-1$ 的二項樹合併：把其中一棵作為另一顆的 Leftmost Child (合併的基礎)
> 補充：
仔細觀察每個 Degree 中各層的 Max Nodes
* $k=0$ -> $1$
* $k=1$ -> $1, 1$
* $k=2$ -> $1, 2, 1$
* $k=3$ -> $1, 3, 3, 1$
正是二項式 $(x+1)^k$ 的展開係數  (帕斯卡三角形)
<br><br>
* **Property：**
1. 符合 Min Tree 的性質：Parent $\leq$ Child
3. 不能有兩棵或以上的二項樹有相同 Degree（包括 Degree 0）
4. 具 Degree $k$ 的二項樹只能有 0 或 1 個
4. 根據 **Def 4**：$Nodes = 2^k$ 得知
* 一顆具有 n Nodes 的二項式堆積，最多只有 $log_2n$ 顆二項樹組成
以上圖來說 Degree 3 二項式堆積由 $log_28=3$ 顆二項樹組成，分別是 Deg-0 , Deg-1 , Deg-2 的二項樹
5. 根據上述性質得知，假設存在 3 顆二項式堆積 Height 分別為 $a,b,c$ ，
則此三顆的 Nodes 合為 $2^a+2^b+2^c$，則我們就可以使用二進制 (Binay) 來表達
* 以下三顆二項式堆積 Height 分別為：$0, 2, 3$
* Nodes 合為：$2^0+2^2+2^3=13$
* $(13)_2=1101$，分別表示相對應的二項樹是否存在
* 承上述性質，若 $Nodes=2^k-1$ 則該堆積則具有 $k$ 個二項樹
---
### Merge - 合併
* 任給兩顆二項樹，發現該高度不一致：$1,2$，所以無法合併，所以該集合數量為 2 是一個 Forest
```graphviz
graph graphname{
10--12
2--5
2--9
9--13
}
```
* 任給三顆二項樹，高度分別為：$1,1,2$
```graphviz
graph graphname{
13--17
9--11
23--24
24--65
23--51
}
```
* 將高度為為 $1$ 的二項樹先合併 (次序無所謂，因此不唯一)，比較 Root ，將比較小的當作新的 Root，並將大的併成他的子樹
```graphviz
graph graphname{
13--17
9--11
}
```
* $9<13$ ， 將 Root 為 13 的二項樹放進 9 為 Root 的二項樹，得到 Height = $2$ 二項樹
```graphviz
graph graphname{
13--17
9--11
9--13
}
```
* 以此類推，繼續判斷並合併
```graphviz
graph graphname{
13--17
9--11
9--13
23--24
24--65
23--51
}
```
* 得到 Height = $3$ 之二項式堆積，Parent 皆 $\leq$ Child
```graphviz
graph graphname{
23--24
24--65
23--51
9--23
9--11
9--13
13--17
}
```
* 設 N 顆二項樹能夠有效的合併成 1 顆完整的二項式堆積，則合併次數為：$\lceil log_2N \rceil=\lceil log_23\rceil=2$
```graphviz
graph graphname{
13--17
9--11
23--24
24--65
23--51
}
```
:::warning
**Time Complexity：**
合併一次：$O(1)$
最多時間：$O(log_2n)$
:::
---
### Insert - 插入
* 依序插入 $1,2,3,4,5,6,7,8$，並討論平均下來的 Time
<br><br><br>
* 插入 1 ，Time Complexity = $O(1)$
```graphviz
graph graphname{
1
}
```
* 插入 2 、合併 1 次，Time Complexity = $O(1)=O(log_22)$
```graphviz
graph graphname{
1--2
}
```
* 插入 3 ，Time Complexity = $O(1)$
```graphviz
graph graphname{
1--2
3
}
```
* 插入 4 、合併 2 次，Time Complexity = $O(log_24)≌O(1)$
```graphviz
graph graphname{
3--4
1--2
1--3
}
```
* 插入 5 ，Time Complexity = $O(1)$
```graphviz
graph graphname{
3--4
1--2
1--3
5
}
```
* 插入 6 、合併 1 次，Time Complexity = $O(1)=O(log_22)$
```graphviz
graph graphname{
3--4
1--2
1--3
5--6
}
```
* 插入 7，Time Complexity = $O(1)$
```graphviz
graph graphname{
3--4
1--2
1--3
5--6
7
}
```
* 插入 8、合併 3 次，Time Complexity = $O(log_28)≌O(1)$
```graphviz
graph graphname{
1--5
7--8
5--6
5--7
3--4
1--2
1--3
}
```
:::warning
**Time Complexity：**
可以看出在資料量小的時候幾乎都是 $O(1)$，而一般正常使用情況還會搭配刪除，
所以大致來說 $O(1)$ 還是占大多數
Worst Case：$O(log_2n)$
Best Case ：$O(1)$ 則是占大多數
此時可以引入一個觀念：平攤成本 $(Amortized Cost)$ 平均下來的成本即為 $O(1)$
:::
---
### Extract Min - 提取最小值
* Best Case：$O(log_2n)$，只有一棵樹且須合併
```graphviz
graph graphname{
1--5
7--8
5--6
5--7
3--4
1--2
1--3
}
```
* Worst Case：$O(log_2n)$，一棵樹以上，也考慮合併
```graphviz
graph graphname{
3--4
1--2
1--3
5--6
7
}
```
:::warning
**Time Complexity：**
$O(log_2n)$，有關最小值的操作：刪除(Delete)、減小(Decrease)都是一樣的
:::
---
### Find Min - 找尋最小值
* 可以使用一個 Pointer：min，在插入時不斷檢查更新，$O(1)$
```graphviz
graph graphname{
min[shape=none]
min--1[constraint=false]
3--4
1--2
1--3
5--6
7
}
```
:::warning
**Time Complexity：**
$O(1)：使用\ Min\ Pointer$
$O(log_2n)：n\ 個\ Node\ 有\ log_2n\ 個\ Root$
:::
---
### Delete Min - 最小值刪除
* 假設此集合有三顆二項樹，接著我們進行刪除
* 當刪除後，以 $2$ 為 Root 的 Child 將各自變成 Root
* 合併結果
```graphviz
digraph graphname{
5->6
3->4
3->5
10->12
}
```
:::warning
**Time Complexity：**
* 將各步驟分解討論
1. 原本 Root 數量為 $a$，刪除 min pointer 指的 Root 後為 $a-1$ 個
2. 而原本 min pointer 指的 Root 有 $b$ 個 Child 會變成 Root
3. 刪除後的 Root 數量為 $a-1+b$ 個
4. 根據 Merge - Worst Case：$O(log_2(a-1+b))=O(log_2n)$
* 指定刪除非 Root 之 Node ，設每顆樹 Nodes = n
* 每顆樹的搜尋時間 $O(log_2n)*c$ 顆二項樹 ≌ $O(log_2n)$
:::
---
### Decrease Data - 減少 Node 值
* 假設減少 Node 8 值至 0
```graphviz
graph graphname{
8[color=red]
1--5
7--8
5--6
5--7
3--4
1--2
1--3
}
```
* 並依序往上檢查是否符合 Min Heap 定義
```graphviz
graph graphname{
7[color=blue]
5[color=blue]
1[color=blue]
1--5
7--0
5--6
5--7
3--4
1--2
1--3
}
```
* 若有需要則不停往上替換
```graphviz
graph graphname{
7[label ="5"]
5[label ="1"]
1[label ="0" color=red]
8[label ="7"]
1--5
7--8
5--6
5--7
3--4
1--2
1--3
}
```
:::warning
**Time Complexity：**
搜尋時間 + 樹高：≌ $O(log_2n)$
:::
| Binomial Heap | Algo (考試) | DS |
| -------- | -------- | -------- |
| Insert | $O(log_2n)$ ，Amortized Time：$O(1)$| $O(1)$ |
| Delete Min | $O(log_2n)$，需考慮合併 | $O(log_2n)$ |
| Merge | $O(log_2n)$ ，Amortized Time：$O(1)$| $O(1)$ 使用 Lazy Merge |
| Extract Min | $O(log_2n)$，使用 min pointer：$O(1)$ | $O(1)$，使用 min pointer |
| Decrease | $O(log_2n)$，需考慮 Heap 性質 | |
Lazy Merge：需要才合併
---
## Reference - 參考資料
* [Wikipedia](https://zh.wikipedia.org/wiki/%E4%BA%8C%E9%A1%B9%E5%A0%86)
###### tags: `Data Structure`
Google Drive
Gist
Clipboard
Sign in with Wallet
