斐波那契堆

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

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

斐波納契堆於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），則去除該標記。

刪除節點

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