# 【資工考研】Fibonacci Heaps
資料結構重點複習摘要
Fibonacci heap 支援 mergeable heap (e.g. Binomial Heap)的各個操作 (`Make-Heap()`, `Insert(H, x)`, `Minimum(H)`, `Extract-Min(H)`, `Union(H1, H2)`)
除此之外 Fibonacci heap 最大的特點在於它有些 operations run in constant amortized time
註： `Make-Heap()` 指建構空 heap
## 時間複雜度比較
| Procedure | Binary heap <br>(worst case) | Fibonacci heap <br>(amortized) |
|:--- |:---:|:---:|
| `Make-Heap` | $\mathrm{\theta} (1)$ | $\mathrm{\theta} (1)$ |
| `Insert` | $\mathrm{\theta} (\lg n)$ | $\mathrm{\theta} (1)$ |
| `Minimum` | $\mathrm{\theta} (1)$ | $\mathrm{\theta} (1)$ |
| `Extract-Min` | $\mathrm{\theta} (\lg n)$ | $\mathrm{\theta} (\lg n)$ |
| `Union` | $\mathrm{\theta} (n)$ | $\mathrm{\theta} (1)$ |
| `Decrease-Key` | $\mathrm{\theta} (\lg n)$ | $\mathrm{\theta} (1)$ |
| `Delete` | $\mathrm{\theta} (\lg n)$ | $\mathrm{\theta} (\lg n)$ |
註： `DECREASE-KEY(H,x,k)` 指將 heap `H` 中的元素 `x` 之值換成不比原本大的值 `k` ，也就是把 `x->val` 變小成 `k`
我們很清楚，一般的 binary heap 在 merge (`Union`) 時的表現可能會不太理想
Fibonacci heap 明顯的優勢就是均攤之下有些操作的表現比較好
可以看到有不少都能達到常數時間
以理論來說，我們這邊談論的場景主要是 `Extract-Min` 跟 `Delete` 兩個操作相對其他操作來得少次的情況，例如在圖論問題中有些演算法會需要對每個邊做 `Decrease-Key`
對於比較密集 (多邊) 的圖， Fibonacci heap 提供的常數時間操作會帶來很大的表現提升
然而回到現實面， Fibonacci heap 寫起來太麻煩了，沒事不會有人想用 (不是說完全沒人用)
考試這邊大概就考觀念，不過本文還是會大致講一下實作部分
## 資料結構
Fibonacci heap 你可以想成是一個 Forest 的資料結構
它是一堆 heap-ordered trees ，也就是每棵樹都滿足父點不大於子點 (the key of a node is greater than or equal to the key of its parent)
> Each node `x` contains a pointer `x.p` to its parent and a pointer `x.child` to any one of its children. The children of `x` are linked together in a circular, doubly linked list, which we call the child list of `x`. Each child `y` in a child list has pointers `y.left` and `y.right` that point to `y`’s left and right siblings, respectively. If node `y` is an only child, then `y.left = y.right = y`. Siblings may appear in a child list in any order.
有了上述性質，我們只要找到 `root` 最小的樹，其 `root` 就是整個 Fibonacci heap 的最小值
用一個指標指向該節點，如此一來 `Minimum` 操作就能是 $\mathrm{\theta} (1)$
兄弟之間會互指 (形成環狀雙向鏈結)，子點都會指向父點，父點會指向自己的其中一個子點
如果是唯一的子點，就會左右指向自己
環狀雙向鏈結串列在這邊有兩個好處：
1. 我們可以在 $O(1)$ 時間內將節點插入到環狀雙向鏈結串列中的任何位置，或從其中的任何位置移除節點
2. 定兩個這樣的串列，我們可以在 $O(1)$ 時間內將它們拼接成一個環狀雙向鏈結串列
除此之外，節點的資料結構還會再包含兩個屬性：
1. `degree`: 節點的子串列節點數
2. `mark`: boolean 值，用來表示該節點是否失去了自己的子節點
Fibonacci heap 要刪或減時都挺麻煩的，上面這邊將在到時候派上用場
```cpp!
template <typename T>
struct FibNode
{
T key;
FibNode *left;
FibNode *right;
FibNode *parent;
FibNode *child;
int degree;
bool mark;
FibNode(T val) : key(val), left(this), right(this), parent(nullptr), child(nullptr), degree(0), mark(false) {}
};
```
另外 Fibonacci heap 本身我們會再紀錄一下有幾個節點
```cpp!
FibNode<T> *minNode;
int nodeCnt;
```
## Potential Function
For a give Fibonacci heap $H$, ew indicate by $t(H)$ the number of trees in the root list of $H$ and by $m(H)$ the number of marked nodes in $H$.
We defined the potential $\phi (H)$ of $H$ by
$$
\phi (H) = t(H) + 2m(H)
$$
Let $D(n)$ be an upper bound on the maximum degree of any node in an $n$ nodes Fibonacci heap, $D(n)\le \left\lfloor \lg n \right\rfloor$
## Union
merge 2 Fibonacci heap 有兩類操作
這邊的 `Union` 精神即 lazy merge
基本就只是把 root 接起來而已，然後看一下現在 min 應該指向誰的
可想而知這邊會是 $O(1)$
```cpp!
// Fib-Heap-Union
void merge(FibonacciHeap<T> &other)
{
lazyMerge(minNode, other.minNode); // 合併 root lists
if (!minNode || (other.minNode && other.minNode->key < minNode->key))
minNode = other.minNode;
nodeCnt += other.nodeCnt;
other.minNode = nullptr;
other.nodeCnt = 0;
}
```
`minNode` 有兩種情況需要變成對方的 `minNode` ：
1. 自己是空的
2. 對方有非空 `minNode` 且它才是最小
那之後就把節點數加起來
## Insert
如果我們把要插入的節點看做一個 Fibonacci heap
`Insert` 不就也是一種 `Union` 嗎？
```cpp!
void insert(T key)
{
FibNode<T> *newNode = new FibNode<T>(key);
lazyMerge(minNode, newNode);
if (!minNode || newNode->key < minNode->key)
minNode = newNode;
++nodeCnt;
}
```
## Minimum
給 `minNode` 就好，這邊很簡單
## Extract-Min
前面都很簡單，這邊開始就真的複雜起來了
我們前面 merge 都用 lazy merge 應付著，但這邊開始我們就需要做 `consolidate` 了
要刪掉最小值的想法還是在 merge ，我們將 `minNode` 的每個子節點都當成 root ，並從 root list 中移除 `minNode`
這個過程你可想成原本的 Fibonacci heap 已經被搞散架了，此時我們需要將有相同度數的 tree 合併，直到不能再合併為止，這個視為一種修復重組，也就是 `consolidate`
```cpp!
T extractMin()
{
if (!minNode)
throw std::runtime_error("Fibonacci heap is empty!");
FibNode<T> *temp = minNode;
if (temp->child)
{
FibNode<T> *child = temp->child;
do
{
child->parent = nullptr;
child = child->right;
} while (child != temp->child);
lazyMerge(minNode, temp->child);
}
temp->left->right = temp->right;
temp->right->left = temp->left;
if (temp == temp->right)
minNode = nullptr;
else
{
minNode = temp->right;
consolidate();
}
--nodeCnt;
T res = temp->key;
delete temp;
return res;
}
```
上面這段 code 中
```cpp!
if (temp->child)
{
FibNode<T> *child = temp->child;
do
{
child->parent = nullptr;
child = child->right;
} while (child != temp->child);
lazyMerge(minNode, temp->child);
}
```
做的就是把 `minNode` 的子點都拆開來，使用 `lazyMerge` 把它們都先加到 root list
```cpp!
temp->left->right = temp->right;
temp->right->left = temp->left;
```
之後，讓 `minNode` 的左右兄弟把手收回來
如果 `minNode` 的右邊指向自己，表示它是 root list 中唯一的那位且它沒有子點
除此之外我們就執行 `consolidate`
## Consolidate
```cpp!
void consolidate()
{
if (!minNode)
return;
int maxDegree = static_cast<int>(std::log2(nodeCnt)) + 1;
std::vector<FibNode<T> *> degreeList(maxDegree, nullptr);
std::vector<FibNode<T> *> rootList;
FibNode<T> *curr = minNode;
do
{
rootList.emplace_back(curr);
curr = curr->right;
} while (curr != minNode);
for (FibNode<T> *node : rootList)
{
int d = node->degree;
while (degreeList[d])
{
FibNode<T> *other = degreeList[d];
if (node->key > other->key)
std::swap(node, other);
link(other, node);
degreeList[d++] = nullptr;
}
degreeList[d] = node;
}
minNode = nullptr;
for (FibNode<T> *tree : rootList)
{
if (tree)
{
if (!minNode || tree->key < minNode->key)
minNode = tree;
}
}
}
```
前面講過 $D(n)\le \left\lfloor \lg n \right\rfloor$
所以 `maxDegree = static_cast<int>(std::log2(nodeCnt)) + 1`
那之後，假設我們在 root list 中找到兩個有相同 `degree` 的節點 `x` 跟 `y` ，不失一般性假設 $x\le y$
那麼為了符合 minimum-heap property ，我們肯定是將 `y` 接給 `x` (使用 `link` 實現)
換句話說： `y` 會從 root list 中拔掉，而 `x` 的 `degree` 會增加
```cpp!
for (FibNode<T> *node : rootList)
{
int d = node->degree;
while (degreeList[d])
{
FibNode<T> *other = degreeList[d];
if (node->key > other->key)
std::swap(node, other);
link(other, node);
degreeList[d++] = nullptr;
}
degreeList[d] = node;
}
```
最後那段是要重新選出 `minNode`
這邊不難看出時間複雜度會是 $O(D(n))$ (即使不實際算 amortized cost 大概也能看出)
## Decrease-Key
```cpp!
void decreaseKey(FibNode<T> *node, T newKey)
{
if (newKey > node->key)
throw std::runtime_error("New key is greater than current key");
node->key = newKey;
FibNode<T> *p = node->parent;
if (p && node->key < p->key)
{
cut(node, p);
cascadingCut(p);
}
if (node->key < minNode->key)
minNode = node;
}
```
我們把某個節點的值變小後，如果它比父點還小，那就破壞我們資料結構的性質了
```cpp!
// cut a node from its parent
void cut(FibNode<T> *node, FibNode<T> *p)
{
if (p->child == node)
p->child = (node->right == node) ? nullptr : node->right;
node->right->left = node->left;
node->left->right = node->right;
--p->degree;
lazyMerge(minNode, node);
node->parent = nullptr;
node->left = node->right = node;
node->mark = false;
}
```
首先我們要先讓該節點與父點訣別 (使用 `cut`)
```cpp!
// cascading cut to maintain properties
void cascadingCut(FibNode<T> *node)
{
FibNode<T> *p = node->parent;
if (p)
{
if (!node->mark)
node->mark = true;
else
{
cut(node, p);
cascadingCut(p);
}
}
}
```
接著就是一直不斷往祖宗那挑戰 (`cascadingCut`)
可以看到在這邊我們才真正用到了 `mark` ，我們透過這個標記來記錄節點的歷史
當某個節點經歷了以下事件：
1. 當 root
2. 當別人子點
3. 失去**第二個子點**時，我們會把它 `cut` 掉
若`x` 經歷了1. 跟 2. 且已經失去一個子點，此時他的 `mark` 會被設成 `true` ，表示它離被 `cut` 掉只差一點點了
實際上就是第一次的 `cascadingCut` 會執行 `if (!node->mark)` 這段，但第二次再來就會執行到 `else` 了
這個動作可以預想，如果 `x` 是 `y` 失去的第二個子點，那 `y` 也要面對上述同樣的事情，對吧？所以這邊還要 `cascadingCut(p)`
另外容易忽略的是，在 `cut` 應該有注意到我們做了 `lazyMerge(minNode, node)`
此時 `node` 又再次經歷 1. ，所以我們要把 `mark` 重置回 `false`
***
假設原本有 $t(H)$ 顆 trees ，有 $c-1$ 顆 trees 經歷 `cascadingCut` 後被拆出來
假設總共有 `c-1` 顆的 `mark` 被 `cascadingCut` unmark ，但最後一次的 `cascadingCut` 可能會再 mark 一個 node ，故最多有 $m(H)-c+2$ 個 marked nodes
則 potential 的變化最多會是：
$$
(t(H)+c-1+1 + 2(m(H)-c+2)) - (t(H)+2m(H)) = 4-c
$$
你會發現， `decreaseKey` 的 amortized cost 最多也就 $O(c)+4-c = O(1)$
Fibonacci 的一大考點就是它 `decreaseKey` 均攤之下僅需常數時間
## Delete
```cpp!
void removeNode(FibNode<T> *node)
{
decreaseKey(node, std::numeric_limits<T>::lowest());
extractMin();
}
```
刪除節點就簡單了，我們只要將要刪除的節點值變成最小，`extractMin` 所刪掉的肯定是該點
## 結尾
最後附上較完整的 code
我沒有認真 debug 過，大概看得懂概念就好，反正考試應該頂多考畫圖🤔
```cpp!
template <typename T>
struct FibNode
{
T key;
FibNode *left;
FibNode *right;
FibNode *parent;
FibNode *child;
int degree;
bool mark;
FibNode(T val) : key(val), left(this), right(this), parent(nullptr), child(nullptr), degree(0), mark(false) {}
};
template <typename T>
class FibonacciHeap
{
public:
FibonacciHeap() : minNode(nullptr), nodeCnt(0) {}
~FibonacciHeap()
{
clear(minNode);
}
void insert(T key)
{
FibNode<T> *newNode = new FibNode<T>(key);
lazyMerge(minNode, newNode);
if (!minNode || newNode->key < minNode->key)
minNode = newNode;
++nodeCnt;
}
// Fib-Heap-Union
void merge(FibonacciHeap<T> &other)
{
lazyMerge(minNode, other.minNode);
if (!minNode || (other.minNode && other.minNode->key < minNode->key))
minNode = other.minNode;
nodeCnt += other.nodeCnt;
other.minNode = nullptr;
other.nodeCnt = 0;
}
T extractMin()
{
if (!minNode)
throw std::runtime_error("Fibonacci heap is empty!");
FibNode<T> *temp = minNode;
if (temp->child)
{
FibNode<T> *child = temp->child;
do
{
child->parent = nullptr;
child = child->right;
} while (child != temp->child);
lazyMerge(minNode, temp->child);
}
temp->left->right = temp->right;
temp->right->left = temp->left;
if (temp == temp->right)
minNode = nullptr;
else
{
minNode = temp->right;
consolidate();
}
--nodeCnt;
T res = temp->key;
delete temp;
return res;
}
void decreaseKey(FibNode<T> *node, T newKey)
{
if (newKey > node->key)
throw std::runtime_error("New key is greater than current key");
node->key = newKey;
FibNode<T> *p = node->parent;
if (p && node->key < p->key)
{
cut(node, p);
cascadingCut(p);
}
if (node->key < minNode->key)
minNode = node;
}
void removeNode(FibNode<T> *node)
{
decreaseKey(node, std::numeric_limits<T>::lowest());
extractMin();
}
private:
FibNode<T> *minNode;
int nodeCnt;
void lazyMerge(FibNode<T> *&h1, FibNode<T> *h2)
{
if (!h1)
h1 = h2;
else if (h2)
{
FibNode<T> *r1 = h1->right, *l2 = h2->left;
h1->right = h2;
h2->left = h1;
r1->left = l2;
l2->right = r1;
}
}
void consolidate()
{
if (!minNode)
return;
int maxDegree = static_cast<int>(std::log2(nodeCnt)) + 1;
std::vector<FibNode<T> *> degreeList(maxDegree, nullptr);
std::vector<FibNode<T> *> rootList;
FibNode<T> *curr = minNode;
do
{
rootList.emplace_back(curr);
curr = curr->right;
} while (curr != minNode);
for (FibNode<T> *node : rootList)
{
int d = node->degree;
while (degreeList[d])
{
FibNode<T> *other = degreeList[d];
if (node->key > other->key)
std::swap(node, other);
link(other, node);
degreeList[d++] = nullptr;
}
degreeList[d] = node;
}
minNode = nullptr;
for (FibNode<T> *tree : rootList)
{
if (tree)
{
if (!minNode || tree->key < minNode->key)
minNode = tree;
}
}
}
void link(FibNode<T> *y, FibNode<T> *x)
{
y->left->right = y->right;
y->right->left = y->left;
y->parent = x;
if (!x->child)
{
x->child = y;
y->left = y;
y->right = y;
}
else
{
FibNode<T> *xchild = x->child;
y->right = xchild;
y->left = xchild->left;
xchild->left->right = y;
xchild->left = y;
}
++x->degree;
y->mark = false;
}
// cut a node from its parent
void cut(FibNode<T> *node, FibNode<T> *p)
{
if (p->child == node)
p->child = (node->right == node) ? nullptr : node->right;
node->right->left = node->left;
node->left->right = node->right;
--p->degree;
lazyMerge(minNode, node);
node->parent = nullptr;
node->left = node->right = node;
node->mark = false;
}
// cascading cut to maintain properties
void cascadingCut(FibNode<T> *node)
{
FibNode<T> *p = node->parent;
if (p)
{
if (!node->mark)
node->mark = true;
else
{
cut(node, p);
cascadingCut(p);
}
}
}
void clear(FibNode<T> *node)
{
if (!node)
return;
FibNode<T> *start = node;
do
{
FibNode<T> *child = node->child;
if (child)
clear(child);
FibNode<T> *next = node->right;
delete node;
node = next;
} while (node != start);
}
};
```
Sign in with Wallet
Connect another wallet