斐波那契堆

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

基本介紹

• 中文名：斐波那契堆
• 外文名：Fibonacci heap
• 途徑：可用於實現合併優先佇列
• 關鍵思想：在於儘量延遲對堆的維護
• 學科：計算機科學
• 領域：計算機科學

簡介

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

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

結構

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

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

斐波那契堆中所有樹的根節點也用一個雙向循環鍊表連結起來。

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

操作

建立一個新的斐波納契堆

每個結點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   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指針連結成一個環形的雙向鍊表，稱為堆的根表。於是，指針min[H]就指向根表中具有最小關鍵字的結點。

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

創建一個空的斐波那契堆，過程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;   }

插入一個節點

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

查找最小的節點

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

合併兩個斐波納契堆

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

釋放（刪除）最小的節點

分為三步：

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

降低一個節點的鍵值

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

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

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

刪除節點

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