斐波那契堆積

斐波那契堆積
類型	堆積
發明時間	1984年
發明者	邁克爾·弗雷德曼、羅伯特·塔揚
用大O符號表示的時間複雜度
演算法 平均 最差 插入 $\Theta (1)$ 尋找最小值 $\Theta (1)$   刪除最小值 $O(\log n)$   減小鍵值 $\Theta (1)$   合併 $\Theta (1)$

斐波那契堆積（英語：Fibonacci heap）是電腦科學中樹的集合。它比二項堆積具有更好的平攤分析效能，可用於實現合併優先佇列。不涉及刪除元素的操作有 $O(1)$ 的平攤時間。 Extract-Min和Delete的數目和其它相比，較小時效率更佳。稠密圖每次decrease key只要 $O(1)$ 的平攤時間，和二項堆積的 $O(logn)$ 相比是巨大的改進。

斐波納契堆積於1984年由邁克爾·弗雷德曼與羅伯特·塔揚提出，1987年公開發表。名字來源於執行時分析使用的斐波那契數。

結構

斐波那契堆積是由一組最小堆積有序樹構成的。每個節點的度數為其子節點的數目。樹的度數為其根節點的度數。

斐波那契堆積中的樹都是有根的但是無序。每個節點x包含指向父節點的指標p[x]和指向任意一個子結點的child[x]。x的所有子節點都用雙向迴圈鏈結串列連結起來，叫做x的子鏈結串列。子鏈結串列中的每一個節點y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果節點y是x僅有的子節點，則left[y]=right[y]=y。

斐波那契堆積中所有樹的根節點也用一個雙向迴圈鏈結串列連結起來。

使用一個指標指向斐波那契堆積中最小元素。

操作

建立一個新的費波那契堆積

此處範例中使用的程式語言為C

每個結點x的域

1. 父結點p[x]
2. 指向任一子女的指標child[x]——結點x的子女被連結成一個環形雙鏈結串列，稱為x的子女表
3. 左兄弟left[x]
4. 右兄弟right[x]——當left[x] = right[x] = x時，說明x是獨子。
5. 子女的個數degree[x]
6. 布林值域mark[x]——標記是否失去了一個孩子

//斐波那契結點ADT
typedef struct FibonacciHeapNode {
    int key;       //結點
    int degree;    //度
    FibonacciHeapNode *left;  //左兄弟
    FibonacciHeapNode *right; //右兄弟
    FibonacciHeapNode *parent; //父結點
    FibonacciHeapNode *child;  //第一個孩子結點
    bool marked;           //是否被刪除第1個孩子
} FibNode;

對於一個給定的斐波那契堆積H，可以通過指向包含最小關鍵字的樹根的指標min[H]來訪問，這個結點被稱為斐波那契堆積中的最小結點。如果一個斐波那契堆積H是空的，則min[H] = NIL. 在一個斐波那契堆積中，所有樹的根都通過left和right指標連結成一個環形的雙向鏈結串列，稱為堆積的根表。於是，指標min[H]就指向根表中具有最小關鍵字的結點。

//斐波那契堆積ADT
typedef struct FibonacciHeap {
    int keyNum;   //堆積中結點個數
    FibonacciHeapNode *min;//最小堆積，根結點
    int maxNumOfDegree;   //最大度
    FibonacciHeapNode **cons;//指向最大度的記憶體區域
} FibHeap;

建立一個空的費波那契堆積，過程MAKE-FIB-HEAP 分配並返回一個費波那契堆積對象H；

//初始化一個空的Fibonacci Heap
FibHeap *FibHeapMake() {
    return calloc(1, sizeof(FibHeap));
}
 
//初始化節點x
FibNode * FibHeapNodeMake() {
    FibNode *x = (FibNode *)calloc(1, sizeof(FibNode));
    x->left = x->right = x;
    return x;
}

插入一個節點

建立一個僅包含一個節點的新的斐波納契堆積，然後執行堆積合併。

尋找最小的節點

由於用一個指標指向了具有最小值的根節點，因此尋找最小的節點是簡單的操作。

合併兩個斐波納契堆積

簡單合併兩個斐波納契堆積的根表。即把兩個斐波納契堆積的所有樹的根首尾銜接並置。

釋放（刪除）最小的節點

分為三步：

1. 尋找最小的根節點並刪除它，其所有的子節點都加入堆積的根表，即它的子樹都成為堆積所包含的樹；
2. 需要尋找並維護堆積的最小根節點，但這耗時較大。為此，同時完成堆積的維護：對堆積當前包含的樹的度數從低到高，迭代執行具有相同度數的樹的合併並實現最小樹化調整，使得堆積包含的樹具有不同的度數。這一步使用一個陣列，陣列下標為根節點的度數，陣列的值為指向該根節點指標。如果發現具有相同度數的其他根節點則合併兩棵樹並維護該陣列的狀態。
3. 對當前堆積的所有根節點尋找最小的根節點。

降低一個節點的鍵值

對一個節點的鍵值降低後，自鍵值降低的節點開始自下而上的迭代執行下述操作，直至到根節點或一個未被標記（marked）節點為止：

如果當前節點鍵值小於其父節點的鍵值，則把該節點及其子樹摘下來作為堆積的新樹的根節點；其原父節點如果是被標記（marked）節點，則也被摘下來作為堆積的新樹的根節點；如果其原父節點不是被標記（marked）節點且不是根節點，則其原父節點被加標記。

如果堆積的新樹的根節點被標記（marked），則去除該標記。

刪除節點

把被刪除節點的鍵值調整為負無窮小，然後執行「降低一個節點的鍵值」演算法，然後再執行「刪除最小節點」演算法。