斐波那契堆的介紹 斐波那契堆(Fibonacci heap)是一種可合並堆，可用於實現合並優先隊列。它比二項堆具有更好的平攤分析性能，它的合並操作的時間復雜度是O(1)。 與二項堆一樣，它也是由一組堆最小有序樹組成，並且是一種可合並堆。 與二項堆不同的是，斐波那契堆中的樹不一定是二項樹；而且二項堆中的樹是有序排列的，但是斐波那契堆中的樹都是有根而無序的。 斐波那契堆的基本操作 1. 基本定義 復制代碼 template <class T> class FibNode { public: T key; // 關鍵字(鍵值) int degree; // 度數 FibNode<T> *left; // 左兄弟 FibNode<T> *right; // 右兄弟 FibNode<T> *child; // 第一個孩子節點 FibNode<T> *parent; // 父節點 bool marked; // 是否被刪除第一個孩子 FibNode(T value):key(value), degree(0), marked(false), left(NULL),right(NULL),child(NULL),parent(NULL) { key = value; degree = 0; marked = false; left = this; right = this; parent = NULL; child = NULL; } }; 復制代碼 FibNode是斐波那契堆的節點類，它包含的信息較多。key是用於比較節點大小的，degree是記錄節點的度，left和right分別是指向節點的左右兄弟，child是節點的第一個孩子，parent是節點的父節點，marked是記錄該節點是否被刪除第1個孩子(marked在刪除節點時有用)。 復制代碼 template <class T> class FibHeap { private: int keyNum; // 堆中節點的總數 int maxDegree; // 最大度 FibNode<T> *min; // 最小節點(某個最小堆的根節點) FibNode<T> **cons; // 最大度的內存區域 public: FibHeap(); ~FibHeap(); // 新建key對應的節點，並將其插入到斐波那契堆中 void insert(T key); // 移除斐波那契堆中的最小節點 void removeMin(); // 將other合並到當前堆中 void combine(FibHeap<T> *other); // 獲取斐波那契堆中最小鍵值，並保存到pkey中；成功返回true，否則返回false。 bool minimum(T *pkey); // 將斐波那契堆中鍵值oldkey更新為newkey void update(T oldkey, T newkey); // 刪除鍵值為key的節點 void remove(T key); // 斐波那契堆中是否包含鍵值key bool contains(T key); // 打印斐波那契堆 void print(); // 銷毀 void destroy(); private: // 將node從雙鏈表移除 void removeNode(FibNode<T> *node); // 將node堆結點加入root結點之前(循環鏈表中) void addNode(FibNode<T> *node, FibNode<T> *root); // 將雙向鏈表b鏈接到雙向鏈表a的後面 void catList(FibNode<T> *a, FibNode<T> *b); // 將節點node插入到斐波那契堆中 void insert(FibNode<T> *node); // 將"堆的最小結點"從根鏈表中移除， FibNode<T>* extractMin(); // 將node鏈接到root根結點 void link(FibNode<T>* node, FibNode<T>* root); // 創建consolidate所需空間 void makeCons(); // 合並斐波那契堆的根鏈表中左右相同度數的樹 void consolidate(); // 修改度數 void renewDegree(FibNode<T> *parent, int degree); // 將node從父節點parent的子鏈接中剝離出來，並使node成為"堆的根鏈表"中的一員。 void cut(FibNode<T> *node, FibNode<T> *parent); // 對節點node進行"級聯剪切" void cascadingCut(FibNode<T> *node) ; // 將斐波那契堆中節點node的值減少為key void decrease(FibNode<T> *node, T key); // 將斐波那契堆中節點node的值增加為key void increase(FibNode<T> *node, T key); // 更新斐波那契堆的節點node的鍵值為key void update(FibNode<T> *node, T key); // 在最小堆root中查找鍵值為key的節點 FibNode<T>* search(FibNode<T> *root, T key); // 在斐波那契堆中查找鍵值為key的節點 FibNode<T>* search(T key); // 刪除結點node void remove(FibNode<T> *node); // 銷毀斐波那契堆 void destroyNode(FibNode<T> *node); // 打印"斐波那契堆" void print(FibNode<T> *node, FibNode<T> *prev, int direction); }; 復制代碼 FibHeap是斐波那契堆對應的類。min是保存當前堆的最小節點，keyNum用於記錄堆中節點的總數，maxDegree用於記錄堆中最大度，而cons在刪除節點時來暫時保存堆數據的臨時空間。下面是斐波那契堆的屬性結構圖和內存結構圖的對比示例。 從中可以看出，斐波那契堆是由一組最小堆組成，這些最小堆的根節點組成了雙向鏈表(後文稱為"根鏈表")；斐波那契堆中的最小節點就是"根鏈表中的最小節點"！ PS. 上面這幅圖的結構和測試代碼中的"基本信息"測試函數的結果是一致的；你可以通過測試程序來親自驗證！ 2. 插入操作 插入操作非常簡單：插入一個節點到堆中，直接將該節點插入到"根鏈表的min節點"之前即可；若被插入節點比"min節點"小，則更新"min節點"為被插入節點。 上面是插入操作的示意圖。 斐波那契堆的根鏈表是"雙向鏈表"，這裡將min節點看作雙向聯表的表頭(後文也是如此)。在插入節點時，每次都是"將節點插入到min節點之前(即插入到雙鏈表末尾)"。此外，對於根鏈表中最小堆都只有一個節點的情況，插入操作就很演化成雙向鏈表的插入操作。 此外，插入操作示意圖與測試程序中的"插入操作"相對應，感興趣的可以親自驗證。 插入操作代碼 復制代碼 /* * 將node堆結點加入root結點之前(循環鏈表中) * a …… root * a …… node …… root */ template <class T> void FibHeap<T>::addNode(FibNode<T> *node, FibNode<T> *root) { node->left = root->left; root->left->right = node; node->right = root; root->left = node; } /* * 將節點node插入到斐波那契堆中 */ template <class T> void FibHeap<T>::insert(FibNode<T> *node) { if (keyNum == 0) min = node; else { addNode(node, min); if (node->key < min->key) min = node; } keyNum++; } 復制代碼 3. 合並操作 合並操作和插入操作的原理非常類似：將一個堆的根鏈表插入到另一個堆的根鏈表上即可。簡單來說，就是將兩個雙鏈表拼接成一個雙向鏈表。 上面是合並操作的示意圖。該操作示意圖與測試程序中的"合並操作"相對應！ 合並操作代碼 復制代碼 /* * 將雙向鏈表b鏈接到雙向鏈表a的後面 * * 注意： 此處a和b都是雙向鏈表 */ template <class T> void FibHeap<T>::catList(FibNode<T> *a, FibNode<T> *b) { FibNode<T> *tmp; tmp = a->right; a->right = b->right; b->right->left = a; b->right = tmp; tmp->left = b; } /* * 將other合並到當前堆中 */ template <class T> void FibHeap<T>::combine(FibHeap<T> *other) { if (other==NULL) return ; if(other->maxDegree > this->maxDegree) swap(*this, *other); if((this->min) == NULL) // this無"最小節點" { this->min = other->min; this->keyNum = other->keyNum; free(other->cons); delete other; } else if((other->min) == NULL) // this有"最小節點" && other無"最小節點" { free(other->cons); delete other; } // this有"最小節點" && other有"最小節點" else { // 將"other中根鏈表"添加到"this"中 catList(this->min, other->min); if (this->min->key > other->min->key) this->min = other->min; this->keyNum += other->keyNum; free(other->cons); delete other; } }
