[科普中國]-斐波那契堆

斐波那契堆(Fibonacci heap)是計算機科學中樹的集合。它比二項式堆具有更好的平攤分析性能，可用于實現合并優(yōu)先隊列。不涉及刪除元素的操作有O(1)的平攤時間。 Extract-Min和Delete的數目和其它相比，較小時效率更佳。

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

斐波納契堆于1984年由Michael L. Fredman與Robert E. Tarjan提出，1987年公開發(fā)表。1名字來源于運行時分析使用的斐波那契數。

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

斐波那契堆中的樹都是有根的但是無序。每個節(jié)點x包含指向父節(jié)點的指針p[x]和指向任意一個子結點的child[x]。x的所有子節(jié)點都用雙向循環(huán)鏈表鏈接起來，叫做x的子鏈表。子鏈表中的每一個節(jié)點y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果節(jié)點y是x僅有的子節(jié)點，則left[y]=right[y]=y。

斐波那契堆中所有樹的根節(jié)點也用一個雙向循環(huán)鏈表鏈接起來。

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

操作建立一個新的斐波納契堆每個結點x的域

父節(jié)點p[x]

指向任一子女的指針child[x]——結點x的子女被鏈接成一個環(huán)形雙鏈表，稱為x的子女表

左兄弟left[x]

右兄弟right[x]——當left[x] = right[x] = x時，說明x是獨子。

子女的個數degree[x]

布爾值域mark[x]——標記是否失去了一個孩子

//斐波那契結點ADT struct FibonacciHeapNode { int key; //結點 int degree; //度 FibonacciHeapNode * left; //左兄弟 FibonacciHeapNode * right; //右兄弟 FibonacciHeapNode * parent; //父結點 FibonacciHeapNode * child; //第一個孩子結點 bool marked; //是否被刪除第1個孩子 }; typedef FibonacciHeapNode FibNode;對于一個給定的斐波那契堆H，可以通過指向包含最小關鍵字的樹根的指針min[H]來訪問，這個結點被稱為斐波那契堆中的最小結點。如果一個斐波那契堆H是空的，則min[H] = NIL. 在一個斐波那契堆中，所有樹的根都通過left和right指針鏈接成一個環(huán)形的雙向鏈表，稱為堆的根表。于是，指針min[H]就指向根表中具有最小關鍵字的結點。

//斐波那契堆ADT struct FibonacciHeap { int keyNum; //堆中結點個數 FibonacciHeapNode * min;//最小堆，根結點 int maxNumOfDegree; //最大度 FibonacciHeapNode * * cons;//指向最大度的內存區(qū)域 }; typedef FibonacciHeap FibHeap; 創(chuàng)建一個空的斐波那契堆，過程MAKE-FIB-HEAP 分配并返回一個斐波那契堆對象H；

//初始化一個空的Fibonacci Heap FibHeap * FibHeapMake() { FibHeap * heap = NULL; heap = (FibHeap *) malloc(sizeof(FibHeap)); if (NULL == heap) { puts("Out of Space!!"); exit(1); } memset(heap, 0, sizeof(FibHeap)); return heap; } //初始化結點x FibNode * FibHeapNodeMake() { FibNode * x = NULL; x = (FibNode *) malloc(sizeof(FibNode)); if (NULL == x) { puts("Out of Space!!"); exit(1); } memset(x, 0, sizeof(FibNode)); x->left = x->right = x; return x; }插入一個節(jié)點創(chuàng)建一個僅包含一個節(jié)點的新的斐波納契堆，然后執(zhí)行堆合并。

查找最小的節(jié)點由于用一個指針指向了具有最小值的根節(jié)點，因此查找最小的節(jié)點是簡單的操作。

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

釋放（刪除）最小的節(jié)點分為三步：

查找最小的根節(jié)點并刪除它，其所有的子節(jié)點都加入堆的根表，即它的子樹都成為堆所包含的樹；

需要查找并維護堆的最小根節(jié)點，但這耗時較大。為此，同時完成堆的維護：對堆當前包含的樹的度數從低到高，迭代執(zhí)行具有相同度數的樹的合并并實現最小樹化調整，使得堆包含的樹具有不同的度數。這一步使用一個數組，數組下標為根節(jié)點的度數，數組的值為指向該根節(jié)點指針。如果發(fā)現具有相同度數的其他根節(jié)點則合并兩棵樹并維護該數組的狀態(tài)。

對當前堆的所有根節(jié)點查找最小的根節(jié)點。

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

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

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

刪除節(jié)點把被刪除節(jié)點的鍵值調整為負無窮小，然后執(zhí)行“降低一個節(jié)點的鍵值”算法，然后再執(zhí)行“刪除最小節(jié)點”算法。

本詞條內容貢獻者為:

王沛 - 副教授、副研究員 - 中國科學院工程熱物理研究所