---
title: 'Fibonacci Heap - 費式堆積'
disqus: hackmd
---
[TOC]

## Fibonacci Heap - 費式堆積 (DS.)
* 先備知識：[Binomial Heap - 二項式堆積](https://hackmd.io/tCv57gtkQJGQxGM3TMo5aA?both#Binomial-Heap---%E4%BA%8C%E9%A0%85%E5%BC%8F%E5%A0%86%E7%A9%8D-Algo)，若以下操作手法相同將不重複解釋
* `Merge - 合併`
* `Pointer：min`

:::danger
費式堆積只要 Height 相同即可合併
:::

* **Def：**
* 是 Extended Binomial Heap
* 與 Binomial Heap 操作相似，但結構並不嚴謹

* | | Binomial Heap | Fibonacci Heap |
| -------- | -------- | -------- |
| 合併時機 | 插入、刪除 | 刪除 |
| 合併性質 | 勤勞的 (Industrious) | 懶惰地 (Lazily) |

* Node 額外的元素
* 指向 Parent 的 Link ， Root 指向 Null
* 指向 Sibling 的 Link (有些版本沒有提)
* Marked (boolean)：檢查該節點是否有失去 Child
* 使用時機
1. 刪除非 Root 之 Node
2. 減少(Decrease) Node Data 後，導致不符合 Min Heap 性質
> 此篇圖例 Null、指向自己之 Link 省略不繪製

<br>

* **Property：**
* 具有 Min Heap 性質

---

### Insert - 插入

* 依序插入 $2,3,4,5,1$，插入 $2$ ，首個元素將 Min 指向它

digraph graphname{
     min[shape=none]
     min->2
}

* 插入 $3$

* $2,3$ 之間為 Sibling Link (記住 Root 也有 Sibling Link)
* <font color=red>每次插入在 min 值的左側</font>

digraph graphname{
     rankdir=RL; 

    { 
    min[shape=none]
    min -> 2 [ constraint=false]; 
    } 
    3[color=red]
    2 -> 3[dir=both]    
}

* 插入 $4$

digraph graphname{
     rankdir=RL; 
    
    { 
    min[shape=none]
    min -> 2 [ constraint=false]; 
    } 
    4[color=red]
    2 -> 4[dir=both]
    4 -> 3[dir=both]
    
}

* 插入 $5$

digraph graphname{
    rankdir=RL; 

    
    min[shape=none]
    min -> 2 [ constraint=false]; 
     
    5 [color=red]
    
    2 -> 5[dir=both]
    5 -> 4[dir=both]
    4 -> 3[dir=both]
}

* 插入 $1$ ， $1$ 為最小值、將 min 指向它

digraph graphname{
    rankdir=RL; 

    { 
    min[shape=none]
    min -> 1 [ constraint=false]; 
    } 
    1 [color=red]
    2 -> 1[dir=both]
    1 -> 5[dir=both]
    5 -> 4[dir=both]
    4 -> 3[dir=both]
}

:::warning
**Time Complexity：**
$O(1)$
:::

---

### Delete Min - 最小值刪除
#### ==刪除 Root==
* 第一次刪除時的情況
* 承上圖例，此時我們經由 min pointer 刪除最小值：$1$

digraph graphname{
    rankdir=RL; 

    { 
    min[shape=none]
    min -> 1 [ constraint=false color=red]; 
    } 
    
    2 -> 1[dir=both]
    1 -> 5[dir=both]
    5 -> 4[dir=both]
    4 -> 3[dir=both]
}

<br><br>

* 更新 min ，之後準備 Pointer：current 依序檢查是否需要合併

digraph graphname{
    rankdir=RL; 

    { 
    min[shape=none]
    current[shape=none]
    min[ constraint=false]; 
    min->2
     
    
    } 
    2 -> 5[dir=both]
    5 -> 4[dir=both]
    4 -> 3[dir=both]
}

<br><br>

* 使用陣列來記錄每個 Root 的 高度

| Height | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- | -------- |
| Min-Heap 數量 | 1 | 0 | 0 | 0 |

digraph graphname{
    rankdir=RL; 

    { 
    min[shape=none]
    current[shape=none]
    min[ constraint=false]; 
    current->3[ color=red constraint=false]; 
    } 
    2 -> 5[dir=both]
    5 -> 4[dir=both]
    4 -> 3[dir=both]
}

<br><br>
* 發現 Height 為 $0$ 的樹有兩顆達到合併條件

| Height | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- | -------- |
| Min-Heap 數量 | 2 | 0 | 0 | 0 |

digraph graphname{
    rankdir=RL; 

    { 
    min[shape=none]
    current[shape=none]
    min[ constraint=false]; 
    current->4[color=red constraint=false]; 
    } 
    2 -> 5[dir=both]
    5 -> 4[dir=both]
    4 -> 3[dir=both]
}

<br><br>
* 依照 Min Heap 合併 Node 3 , Node 4，調整對應的 Height 數量

| Height | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- | -------- |
| Min-Heap 數量 | 0 | 1 | 0 | 0 |


<br><br>

| Height | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- | -------- |
| Min-Heap 數量 | 1 | 1 | 0 | 0 |


<br><br>

| Height | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- | -------- |
| Min-Heap 數量 | 2 | 1 | 0 | 0 |
* 發現 Height 為 $0$ 的樹有兩顆，達到合併條件


<br><br>
* 依照 Min Heap 合併 Node 2 , Node 5，調整對應的 Height 數量

| Height | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- | -------- |
| Min-Heap 數量 | 0 | 2 | 0 | 0 |
* 發現 Height 為 $1$ 的樹有兩顆達到合併條件


<br><br>
* 進行合併，調整對應的 Height 數量
* 調整 min pointer

| Height | 0 | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- | -------- |
| Min-Heap 數量 | 0 | 0 | 1 | 0 |

digraph graphname{

    3->4
    2->5
    2->3
    
    min[shape=none]
    current[shape=none]
    min[ constraint=false]; 
    current[color=red constraint=false]; 
    min->2[color=red]
}

---

#### ==刪除非 Root==

* 第一次刪除後，還是有機會再次刪到 Degree 0 Node ，此處以刪除 Degree > 0 Node 為例子

* 假設此集合有兩顆 Min-Heap，接著我們進行最小刪除


* 當我們刪除後
* 以 $2$ 為 Root 的 Child 將各自變成 Root
* 並且與其它的 Root 一起合併 (meld) 並建立 Sibling 關係
* 將 min 指向正確位置
* 沒有達到合併條件，結束


:::warning
**Time Complexity：**
* 將各步驟分解討論
1. 原本 Root 數量為 $a$，刪除 min pointer 後為 $a-1$ 個
2. min pointer 指的 Node 有 $b$ 個新 Root (Child) 要加入
3. 則總共的 Root 為 $a-1+b$ 個

* 根據 Merge 之 Big-O：$O(log_2(a-1+b))=O(log_2n)$
* 如果是指定刪除某 Node ，設每顆樹 Nodes = n
* 每顆樹的搜尋時間 $log_2n*c$ 顆 Min-Heap ≌ $O(log_2n)$
:::

---

### Marked - 標記

* 若刪除非 Root 之 Node 勢必會破壞 Min-Heap 的結構，所以特地使用 `Boolean：mark` 來判斷該 Node 是否有遺失 Child
* 第一次喪子，Mark 該 Node Parent ：`mark = true`
* 第二次相同 Parent 喪子則將該 Node 合併 (meld) 至 Root，並 Unmark：`mark = false`
* 若 Parent 為 Root 則不需要使用 `mark`
<br><br>
* 刪除 Node 9

digraph graphname{

    3->4
    2->5
    2->3
    3->6
    4->9
    4->12
    9[color=red]
    min[shape=none]
    min[ constraint=false];
    min->2
}

* Node 4->mark =true

digraph graphname{

    3->4
    2->5
    2->3
    3->6
    4->12
    4[style=filled]
    min[shape=none]
    min[ constraint=false];
    min->2
}

* 刪除 Node 6

digraph graphname{

    3->4
    2->5
    2->3
    3->6
    6[color=red]
    4[style=filled]
    4->12
    min[shape=none]
    min[ constraint=false];
    min->2
}

* Node 3->mark =true

digraph graphname{

    3->4
    2->5
    2->3
    4->12
    3[style=filled]
    4[style=filled]
    min[shape=none]
    min[ constraint=false];
    min->2
}

* 刪除 Node 12

digraph graphname{

    3->4
    2->5
    2->3
    4->12
    12[color=red]
    3[style=filled]
    4[style=filled]
    min[shape=none]
    min[ constraint=false];
    min->2
}

* Node 4->mark 已經為 true

digraph graphname{

    3->4
    2->5
    2->3
    3[style=filled]
    4[style=filled color=red]
    min[shape=none]
    min[ constraint=false];
    min->2
}

* 將 Node 4 meld 至 Root，並且 Unmark Node 4

* 同時間，Node 3 也失去 Node 4，但 Node 3->mark 已經為 true


* 將 Node 3 meld 至 Root，並且 Unmark Node 3


* 檢查並合併


---

### Decrease Data - 減少 Node 值

* 首先將 Node 12 Decrease 至 10

digraph graphname{

    3->4
    2->5
    2->3
    3->6
    4->9
    4->12
    12->15
    12[color=red]
    min[shape=none]
    min[ constraint=false];
    min->2
}

* 並無影響 Min-Heap 性質，無須更動

digraph graphname{

    3->4
    2->5
    2->3
    3->6
    4->9
    4->10
    10->15
    10[color=red]
    min[shape=none]
    min[ constraint=false];
    min->2
}

* 接著將 Node 10 Decrease 至 1

digraph graphname{

    3->4
    2->5
    2->3
    3->6
    4->9
    4->1
    1->15
    1[color=red]
    min[shape=none]
    min[ constraint=false];
    min->2
}

<br>

* 不符合 Min-Heap 性質，將 Node 1 meld 至 Root


<br>

* 並記得 Mark 失去 Child 的 Parent：Node 4，以及調整 min pointer


:::warning
**Time Complexity：**
更改 Data 值：O(1)
移動至 Root list：O(1)
:::

| Operation | Time |
| -------- | -------- |
| Merge | $O(log_2n)$ |
| Insert | $O(1)$ ，Lazily Merge|
| Extract Min | $O(log_2n)$|
| Find Min | $O(1)$，使用 min pointer |
| Delete Min | $O(log_2n)$，需考慮合併 |
| Decrease | $O(1)$ |
## Reference - 參考

* [Princeton University](https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf)
* [Algorithm Visualizations](https://www.cs.usfca.edu/~galles/visualization/FibonacciHeap.html)
* [Wikipedia](https://en.wikipedia.org/wiki/Fibonacci_heap#cite_note-amortized-7)

###### tags: `Data Structure`