【資工考研】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 (worst case)	Fibonacci heap (amortized)
`Make-Heap`	$θ (1)$	$θ (1)$
`Insert`	$θ (\lg n)$	$θ (1)$
`Minimum`	$θ (1)$	$θ (1)$
`Extract-Min`	$θ (\lg n)$	$θ (\lg n)$
`Union`	$θ (n)$	$θ (1)$
`Decrease-Key`	$θ (\lg n)$	$θ (1)$
`Delete`	$θ (\lg n)$	$θ (\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)

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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 操作就能是

θ (1)

兄弟之間會互指 (形成環狀雙向鏈結)，子點都會指向父點，父點會指向自己的其中一個子點
如果是唯一的子點，就會左右指向自己

環狀雙向鏈結串列在這邊有兩個好處：

我們可以在
$O (1)$ 時間內將節點插入到環狀雙向鏈結串列中的任何位置，或從其中的任何位置移除節點
定兩個這樣的串列，我們可以在
$O (1)$ 時間內將它們拼接成一個環狀雙向鏈結串列

除此之外，節點的資料結構還會再包含兩個屬性：

degree: 節點的子串列節點數
mark: boolean 值，用來表示該節點是否失去了自己的子節點

Fibonacci heap 要刪或減時都挺麻煩的，上面這邊將在到時候派上用場

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 本身我們會再紀錄一下有幾個節點

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

ϕ (H)

H

ϕ (H) = t (H) + 2 m (H)

Let

D (n)

be an upper bound on the maximum degree of any node in an

n

nodes Fibonacci heap,

D (n) \leq ⌊ \lg n ⌋

Union

merge 2 Fibonacci heap 有兩類操作

這邊的 Union 精神即 lazy merge

基本就只是把 root 接起來而已，然後看一下現在 min 應該指向誰的

可想而知這邊會是

O (1)

    // 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 ：

自己是空的
對方有非空 minNode 且它才是最小

那之後就把節點數加起來

Insert

如果我們把要插入的節點看做一個 Fibonacci heap

Insert 不就也是一種 Union 嗎？

    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

    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 中

        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

        temp->left->right = temp->right;
        temp->right->left = temp->left;

之後，讓 minNode 的左右兄弟把手收回來

如果 minNode 的右邊指向自己，表示它是 root list 中唯一的那位且它沒有子點
除此之外我們就執行 consolidate

Consolidate

    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) \leq ⌊ \lg n ⌋

所以 maxDegree = static_cast<int>(std::log2(nodeCnt)) + 1

那之後，假設我們在 root list 中找到兩個有相同 degree 的節點 x 跟 y ，不失一般性假設

x \leq y

那麼為了符合 minimum-heap property ，我們肯定是將 y 接給 x (使用 link 實現)

換句話說： y 會從 root list 中拔掉，而 x 的 degree 會增加

        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

    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;
    }

我們把某個節點的值變小後，如果它比父點還小，那就破壞我們資料結構的性質了

    // 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)

    // 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 ，我們透過這個標記來記錄節點的歷史

當某個節點經歷了以下事件：

當 root
當別人子點
失去第二個子點時，我們會把它 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) + 2 m (H)) = 4 - c

你會發現， decreaseKey 的 amortized cost 最多也就

O (c) + 4 - c = O (1)

Fibonacci 的一大考點就是它 decreaseKey 均攤之下僅需常數時間

Delete

    void removeNode(FibNode<T> *node)
    {
        decreaseKey(node, std::numeric_limits<T>::lowest());
        extractMin();
    }

刪除節點就簡單了，我們只要將要刪除的節點值變成最小，extractMin 所刪掉的肯定是該點

結尾

最後附上較完整的 code
我沒有認真 debug 過，大概看得懂概念就好，反正考試應該頂多考畫圖🤔

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);
    }
};

【資工考研】Fibonacci Heaps

時間複雜度比較

資料結構

Potential Function

Union

Insert

Minimum

Extract-Min

Consolidate

Decrease-Key

Delete

結尾

Read more

DM Generating Function

DSA Search & Sort

DM 遞迴關係式

DM 二元關係