## Fibonacci Heap


### Definition
1. 由很多個 rooted tree 組合而成，而每棵 tree 都具 Min Heap property
2. <font color = "snake">**root list**</font>: 用Circular doubly linked list 串連所有的 root
4. <font color = "snake">**Child list**</font>: 用Circular doubly linked list 串連所有的 child

>用Circular doubly linked list的好處：
>>insert、 remove某個node, concatenate兩個doubly linked list，time皆為O(1)

---
- 如果某個 node x 只有一個 child y
>y.left = y.right = y
- child list 裡的 sibling 順序是任意的
- 要 access Fib Heap 時要用一個 pointer <font color = "snake">**H.min**</font> 指向含 min key 的 node

- 如果有多個 node key 都是min：任選
- 如果 Fib Heap 為空：Nil

---
### Time Complexity

- decrease key, delete require指向要operate的node的pointer

:::info
$D(n) :=$ 一個具 n 個 node 的 Fib Heap 中最大的 deg
:::
><font color = "red">D(n) = O(logn)</font>

Root list 的大小最多是 D(n) + 1 = O(logn) + 1
因此 <font color = "red">Extract-Min = O(logn) </font>
*（extract 之後要從 root list 找下個 Min）*

- Extract-min 和 min 不同
- Min 只會回傳 min key 的 pointer
- Extract-min 會刪 min element 再 return

---
### Operations
:::success
#### Insert
:::
<font color = "red">O(1)</font>
1. 直接把要 insert 的 node 放到 root list


:::success
#### Union
:::
<font color = "red">O(1)</font>
1. 把 H.min（合併後新 Fib Heap 的 min）先設 H1.min
2. 把 H1, H2 兩個 root list 合併
3. 如果 H1 為空，或 H2.min < H1.min，再把 H.min 改成 H2.min

:::success
#### Extract min（假設 Fib Heap 非空）
:::
<font color = "red">O(logn)</font>
1. 把 min node 的每個 child 加到root list
2. 刪掉 min
3.
- 如果本來就只有一個 node (min node 的 pointer 指向自己)，把min 設成 Nil
- 如果本來不止一個 node，把 min 設成 min 的 rpointer 指向的node
4. Consolidate

>每次 extract min 時，因為某個 root 會被刪（因為有 min heap property，所以被刪的一定是某個 root），會把這個 root 底下的 child 都加到 root list，為了不要讓 root list 太大，在這之後我們會做 consolidate（合併），直到每棵 min heap 的 deg 不同為止。

:::success
##### Consolidate
:::
1. 從 root list 裡找 deg 相同的兩個 node x, y，假設 x.key < y.key
2. 把 y 從root list 刪除，把 y 變成 x 的child (此步稱作 Link)
>重複這兩步，直到 root list 裡所有 root 的 deg 都不同

- 我們用額外的array A[0..D(n)] 來記錄 root 的 deg
- 如果 A[i] = y，代表 y 目前的deg = i
>A的 index 到 D(n) 是因為 D(n) 代表整個Fib Heap 裡的 max deg，所以任何 root 的 deg 最大就是 D(n)

##### 例子
1. 對 (a) 的 Fib Heap 執行一次 extract-min
2. (b) 把 min node 3 底下的 children 加到 root list，且把 min 設成原本的 min = 3 右邊的 17
3. (e) 目前 A 裡已記錄 deg = 0, 1, 2 的 root
4. 下一個檢查 7 的 deg 發現 deg(7) = deg(23) = 0，且 7<23
- 把 23 變成 7 的 child
5. (g) deg(7) = deg(17) = 1，且 7<17
- 把 17（17, 30）變成 7（7, 23）的 child
6. (h) deg(7) = deg(24) = 2，且 7<24
- 把 24（24, 46, 26, 35）變成 7（7, 17, 23, 30）的 child


7. (i) deg(52) = deg(21) = 0，且 21<52
- 把 52 變成 21 的 child（圖中略）
8. (k) deg(18) = deg(21) = 1，且 18<21
- 把 21(21, 52) 變成 18(18, 39) 的 child

至此圖中的 rooted tree deg 皆不相同（由左而右為 3, 2, 1），完成 Consolidate

:::success
#### Decrease-key
:::
<font color = "red">O(1)</font>
1. 確認新 key 值 < 原 key 值，否則回傳 error
2. 設新 key 值
3.
- 如果要 decrease 的 node 就是 root，或 decrease 後的 key 值大於等於 parent 的 key 值 *（沒破壞 min heap property）*
- 直接跳到 4
- 如果要 decrease 的 node 有 parent，且 decrease 後的 key 值小於 parent 的 key 值 *(破壞 min heap property)*
- 執行 `cut` 和 `cascading-cut`
> 見下方說明
4. 確認 H.min 有沒有在 Decrease-key 後改變

詳細說明與 pseudocode：

> - line 1,2：如果要賦予 $x$ 的新 key 值比 $x$ 原本的值來的小，就違反了 decrease key 的定義（新 key $<$ 原 key），因此 report error
> - line 3：如果前面檢查完新的 key 值確實比較小，就將這個值 $k$ 令為 $x$ 的 key。
> - line 4：我們要檢查 $x$ 的值變小後，它的值會不會反而比它的 parent 更小，因此將 $x$ 的 parent 值令為 $y$。
> - line 5：有可能其實 $x$ 根本就沒有 parent，因此如果有（`y != NIL`），且真的有 $y > x$ 的情形，那我們就往下執行 line 6, 7 的 `cut` 和 `cascading-cut`。
>> 說明見更下方。
>
> - line 8：假設上方都執行完畢，現在 $x$ 的值已經是 decreased key $k$，我們就需要接著檢查這個值有沒有比它所在的 heap $H$ 原本的最小值還要小。
> - line 9：如果 $k <$ `H.min.key`，那就把新的最小值設成 $k$，也就是 updated 後的 $x$。

在上面的 pseudocode 中，line 6, 7 的 `cut` 和 `cascading-cut` 之所以會發生，是因為 line 5「違反 min property」的條件檢查成立，所以當 child 比 parent 小時，我們首先做 `cut`：


也就是我們直接把 key 變小的 $x$ 從它的 parent $y$ 的 child list 中移除，因為少了一個 child，所以 $y$ 的 degree 也要減一，那這個被移除的 $x$ 就會直接上移到 root list。作為一個 root，$x$ 當然是沒有 parent，所以 `x.p = NIL`，且 mark 要設為 false。
> 下面會再對 mark 的作用多做說明。

執行完這個 `cut` 以後，如果回過頭去看 `decrease-key` 的 line 7，會發現我們還要做一個 `Cascading-cut(H,y)`。
- Note：是對剛剛 $x$ 的 parent $y$ 做 cascading cut。

> - line 1：檢查 $y$ 有沒有 parent，如果沒有，代表 $y$ 自己本來就是 root，所以在前面 $x$ 從它的 child list 中移走以後，我們就不用再做任何處理。
> - line 2：因此，建立在 $y$ 並非 root 的情況下我們再進一步去做後面的檢查。

接下來我們會去檢查 $y$ 的 `mark` 是 true 還是 false，因此就要先對 `mark` 是什麼做說明：

`x.mark`：是一個 boolean value，代表一個 node $x$ 從上次它被變成別的 node 的 child 以來，它是否有再失去任何 child。

中文有點拗口，原文為：
:::info
The boolean-valued attribute `x.mark` indicates whether node $x$ has lost a child since the last time $x$ was made the child of another node.
:::

一開始所有新的 nodes 的 mark 初值都是 false，那如果一個 node 要從 marked 變成 unmarked，唯有它被變成別的 node 的 child 時。

或許我們先繼續看 `cascading-cut` 後面幾行，看完會更明白 mark 到底在做什麼。

像剛才說的，一開始所有的 nodes 初值都是 false，所以我們可以想像：

一個 node $y$ 假如一開始有兩個 child，在其中一個 child $x$ 從它的 child list 中移除時，我們第一次執行到這個`cascading-cut`，所以在 line 3 時 `y.mark` 本來確實是 false，因此條件成立，於是我們執行 line 4 把 $y$ 的 mark 設成 true，代表它有一個小孩已經被移除了。

假設在某一步我們再度做 decrease key，然後 $y$ 的另一個 child 的值又被調得比 $y$ 要來的小，那麼 $y$ 的另外這個小孩也會被用 `cut` 移除，然後我們第二次對 $y$ 執行到 `cascading-cut`，這個時候 `y.mark != FALSE`，因此我們跳到 line 5：

line 5：`Cut(H,y,z)`
> 將 $y$ 從它的 parent $z$ 的 child list 中移除，$y$ 自己移到 root，做 `cut` 中其他檢查等動作。

line 6：`Cascading-cut(H,z)`
> 回過頭來再去 recursively 對 $y$ 的 parent $z$ 做同樣的事（如果 $y$ 是第一個 $z$ 失去的小孩就 mark，不是就 cut $z$ 移到 root，再檢查 $z$ 的 parent⋯⋯。）

我們就會這樣不斷做下去，直到某個 parent 它原本是 unmark，所以 mark 完就結束，或是直到我們一路找到 root（這樣的話某個 node 的 parent 就是 `NIL`，`cascading-cut` 的 line 3~6 就也不用執行。）

如果我們回過頭去看 `decrease-key` 的 code，就會發現在 `cascading-cut` 做完以後，中間可能有一些 node 移到 root，但我們才只去檢查 `H.min.key` 和 `x.key`，這會影響嗎？

其實也不會，因為從頭到尾就只有 $x$ 的 key 被 decrease 了，所以不管其他 node 移到什麼地方去，唯一有可能讓整個 heap 的最小值改變的仍然只有 $x$。

:::success
#### Delete
:::
<font color = "red">O(logn)</font>
1. 把要 delete 的 node decrease-key 成 key 值負無限大：O(1)
2. Extract-min：O(logn)