-
斐波那契堆
鎖定
目錄
斐波那契堆簡介
斐波那契堆(Fibonacci heap)是計算機科學中樹的集合。它比二項式堆具有更好的平攤分析性能，可用於實現合併優先隊列。不涉及刪除元素的操作有O(1)的平攤時間。 Extract-Min和Delete的數目和其它相比，較小時效率更佳。稠密圖每次decrease key只要O(1)的平攤時間，和二項堆的O(lg n)相比是巨大的改進。
斐波那契堆結構
斐波那契堆是由一組最小堆有序樹構成的。每個節點的度數為其子節點的數目。樹的度數為其根節點的度數。
斐波那契堆中的樹都是有根的但是無序。每個節點x包含指向父節點的指針p[x]和指向任意一個子結點的child[x]。x的所有子節點都用雙向循環鏈表鏈接起來，叫做x的子鏈表。子鏈表中的每一個節點y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果節點y是x僅有的子節點，則left[y]=right[y]=y。
斐波那契堆中所有樹的根節點也用一個雙向循環鏈表鏈接起來。
使用一個指針指向斐波那契堆中最小元素。
斐波那契堆操作
斐波那契堆建立一個新的斐波納契堆
每個結點x的域
- 父節點p[x]
- 指向任一子女的指針child[x]——結點x的子女被鏈接成一個環形雙鏈表，稱為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指針鏈接成一個環形的雙向鏈表，稱為堆的根表。於是，指針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; }斐波那契堆插入一個節點
創建一個僅包含一個節點的新的斐波納契堆，然後執行堆合併。
斐波那契堆查找最小的節點
由於用一個指針指向了具有最小值的根節點，因此查找最小的節點是簡單的操作。
斐波那契堆合併兩個斐波納契堆
簡單合併兩個斐波納契堆的根表。即把兩個斐波納契堆的所有樹的根首尾銜接並置。
斐波那契堆釋放（刪除）最小的節點
分為三步：
- 查找最小的根節點並刪除它，其所有的子節點都加入堆的根表，即它的子樹都成為堆所包含的樹；
- 需要查找並維護堆的最小根節點，但這耗時較大。為此，同時完成堆的維護：對堆當前包含的樹的度數從低到高，迭代執行具有相同度數的樹的合併並實現最小樹化調整，使得堆包含的樹具有不同的度數。這一步使用一個數組，數組下標為根節點的度數，數組的值為指向該根節點指針。如果發現具有相同度數的其他根節點則合併兩棵樹並維護該數組的狀態。
- 對當前堆的所有根節點查找最小的根節點。
斐波那契堆降低一個節點的鍵值
對一個節點的鍵值降低後，自鍵值降低的節點開始自下而上的迭代執行下述操作，直至到根節點或一個未被標記（marked）節點為止：
如果當前節點鍵值小於其父節點的鍵值，則把該節點及其子樹摘下來作為堆的新樹的根節點；其原父節點如果是被標記（marked）節點，則也被摘下來作為堆的新樹的根節點；如果其原父節點不是被標記（marked）節點且不是根節點，則其原父節點被加標記。
如果堆的新樹的根節點被標記（marked），則去除該標記。
斐波那契堆刪除節點
把被刪除節點的鍵值調整為負無窮小，然後執行“降低一個節點的鍵值”算法，然後再執行“刪除最小節點”算法。
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：14次歷史版本
- 最近更新： 一碗加糖饭