优先队列3大利器——二项堆、斐波那契堆、Pairing 堆

优先队列三大利器——二项堆、斐波那契堆、Pairing 堆

优先队列三大利器——二项堆、斐波那契堆、Pairing 堆

本文内容框架：

写在前面的话

二项堆

二项堆的定义，操作，实现

斐波那契堆

斐波那契堆的定义，操作，实现

Pairing堆

Pairing 堆的定义，操作，实现

小结

写在前面的话

昨天发现，作者辛苦的劳动被一个无耻的人给窃取了——有一个人（csdn ID :qiaqia609）（希望能引以为戒）在CSDN上把本人的很多博文完全粘贴复制过去，直接发表在上竟然标注是原创，有图有真相（链接：http://blog.csdn.net/qiaqia609/article/month/2012/10）

优先队列3大利器——二项堆、斐波那契堆、Pairing 堆

竟然有一篇我在 iteye的博客都没有上首页，在CSDN首页竟然被置顶了，本人顿时很恼火，一度不想继续写下去，严重谴责这种不道德的行为，不敢说什么版权，但是这至少本人的辛苦劳作，很多都写到半夜，所以希望人人能有点意识，支持原创（在另一篇博客有详细叙述）。

好吧，虽然昨晚心情一直没有平复，但是总归还是要写，还是要学习。这篇博文主要介绍二项堆、斐波那契堆、Pairing 堆，都知道只要这三个结构应用实现优先队列的，讲解还是比较详细，参考了很多资料，尤其是Pairing堆很少有讲解，但还是力所能及的写了，虽然可能正确很难保证，其次就是斐波那契堆我对于减小一个关键字的操作的级联剪枝不是很理解（不知道为什么要这么做，难道是为了追求好的时间复杂度）还望高人指点，具体细节在下文会有很多介绍。

下面对这三者进行对比

其中(*)Amortized time
(**)With trivial modification to store an additional pointer to the minimum element
(***)Where n is the size of the larger heap
优先队列3大利器——二项堆、斐波那契堆、Pairing 堆

二项堆（Binomial Heap）

二项堆（Binomial Heap）是二项树（Binomial Tree）的集合（collection），所以势必要先简要介绍下二项树。关于堆（最小堆）的相关知识，作者已经在堆排序有介绍可以点击查看，这里就不多枚举了。

二项树（Binomial Tree）

二项树（Binomial Tree）是一组多分支树的序列，二项树的递归定义：

二项树的第0棵树只有一个结点；二项树的第K棵树的子结点由二项树的前面k-1棵组成的。

优先队列3大利器——二项堆、斐波那契堆、Pairing 堆

从以上定义，不难得到下面的结论：

二项树的第K棵树有?2^{k个结点，高度是k；深度为 d 的结点共有个结点（从上图就可以看出结点是按二项分布的(1,3,3,1)）二项堆由一组二项树所构成，这里的二项树需要满足下列条件：
1）H中的每个二项树遵循最小堆的性质。
2）对于任意非负整数k，在H中至多有一棵二项树的根具有度数k。
?
对于性质2，任意高度最多有一棵二项树，这样就可以用二项树的集合唯一地表示任意大小的二项堆，比如13个结点的二项堆H，13的二进制表示为（1101），故H包含了最小堆有序二项树B3， B2和B0，他们分别有8， 4， 2， 1个结点，即共有13个结点。如下图（另外：二项堆中各二项树的根被组织成一个链表，称之为根表）
二项树的ADT
?
typedef struct BinHeapNode BinNode;typedef struct BinHeapNode * BinHeap;typedef struct BinHeapNode * Position; //结点ADTstruct BinHeapNode { int key; int degree; Position parent; Position leftChild; Position sibling;};
?
二项dui的操作
1）创建二项堆?
?
BinHeap MakeBinHeap() { BinHeap heap = NULL; heap = (BinHeap) malloc(sizeof(BinNode)); if (heap == NULL) { puts("Out of the Space"); exit(1); } memset(newHeap, 0, sizeof(BinNode)); return heap;}
?
2）寻找最小关键字
由于每一个二项树都满足最小堆的性质，所以每个二项树的最小关键字一定在根结点，故只需遍历比较根表的情况就可以。
//返回最小根节点的指针BinHeap BinHeapMin(BinHeap heap) { Position y = NULL, x = heap; int min = INT_MAX; while (x != NULL) { if (x->key < min) { min = x->key; y = x; } x = x->sibling; } return y;}
3）合并两个二项堆
合并两个二项堆有三个函数：
?
BINOMIAL-LINK，连接操作，即将两棵根节点度数相同的二项树Bk-1连接成一棵Bk。伪代码：
BINOMIAL-HEAP-MERGE ，将H1和H2的根表合并成一个按度数的单调递增次序排列的链表。
BINOMIAL-HEAP-UNION，反复连接根节点的度数相同的各二项树。伪代码：
合并操作分为两个阶段：
第一阶段：执行BINOMIAL-HEAP-MERGE，将两个堆H1和H2的根表合并成一个链表H，它按度数排序成单调递增次序。MERGE的时间复杂度O(logn)。n为H1和H2的结点总数。（对于每一个度数值，可能有两个根与其对应，所以第二阶段要把这些相同的根连起来）。
第二阶段：将相等度数的根连接起来，直到每个度数至多有一个根时为止。执行过程中，合并的堆H的根表中至多出现三个根具有相同的度数。（MERGE后H中至多出现两个根具有相同的度数，但是将两个相同度数的根的二项树连接后，可能与后面的至多两棵二项树出现相同的度数的根，因此至多出现三个根具有相同的度数）
?
第二阶段根据当前遍历到的根表中的结点x，分四种情况考虑:
Case1：degree[x] != degree[sibling[x]]。此时，不需要做任何变化，将指针向根表后移动即可。(下图示a)
Case2：degree[x] == degree[sibling[x]] == degree[sibling[sibling[x]]]。此时，仍不做变化，将指针后移。(下图示b)
Case3 & Case4：degree[x] = degree[sibling[x]] != degree[sibling[sibling[x]]] (下图示c和d)
Case3：key[x] <= key[sibling[x]]。此时，将sibling[x]连接到x上。
Case4：key[x] > key[sibling[x]]。此时，将x连接到sibling[x]上。
复杂度：O(logn)，四个过程变化情况：
?
?
//两个堆合并BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2) { Position heap = NULL, pre_x = NULL, x = NULL, next_x = NULL; heap = BinHeapMerge(H1, H2); if (heap == NULL) { return heap; } pre_x = NULL; x = heap; next_x = x->sibling; while (next_x != NULL) { if ((x->degree != next_x->degree) ||//Cases 1 and 2 ((next_x->sibling != NULL) && (next_x->degree == next_x->sibling->degree))) { pre_x = x; x = next_x; } else if (x->key <= next_x->key) {//Cases 3 x->sibling = next_x->sibling; BinLink(next_x, x); } else {//Cases 4 if (pre_x == NULL) { heap = next_x; } else { pre_x->sibling = next_x; } BinLink(x, next_x); x = next_x; } next_x = x->sibling; } return heap;} //将H1, H2的根表合并成一个按度数的单调递增次序排列的链表BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2) { //heap->堆的首地址，H3为指向新堆根结点 BinHeap heap = NULL, firstHeap = NULL, secondHeap = NULL, pre_H3 = NULL, H3 = NULL; if (H1 != NULL && H2 != NULL){ firstHeap = H1; secondHeap = H2; //整个while，firstHeap, secondHeap, pre_H3, H3都在往后顺移 while (firstHeap != NULL && secondHeap != NULL) { if (firstHeap->degree <= secondHeap->degree) { H3 = firstHeap; firstHeap = firstHeap->sibling; } else { H3 = secondHeap; secondHeap = secondHeap->sibling; } if (pre_H3 == NULL) { pre_H3 = H3; heap = H3; } else { pre_H3->sibling = H3; pre_H3 = H3; } if (firstHeap != NULL) { H3->sibling = firstHeap; } else { H3->sibling = secondHeap; } }//while } else if (H1 != NULL) { heap = H1; } else { heap = H2; } H1 = H2 = NULL; return heap;} //使H2成为H1的父节点void BinLink(BinHeap &H1, BinHeap &H2) { H1->parent = H2; H1->sibling = H2->leftChild; H2->leftChild = H1; H2->degree++;}
4）插入一个结点
先创建只有该结点的二项堆，然后在与原来的二项堆合并。
//用数组内的值建堆BinHeap MakeBinHeapWithArray(int keys[], int n) { BinHeap heap = NULL, newHeap = NULL; for (int i = 0; i < n; i++) { newHeap = (BinHeap) malloc(sizeof(BinNode)); if (newHeap == NULL) { puts("Out of the Space"); exit(1); } memset(newHeap, 0, sizeof(BinNode)); newHeap->key = keys[i]; if (NULL == heap) { heap = newHeap; } else { heap = BinHeapUnion(heap, newHeap); newHeap = NULL; } } return heap;}
5）删除最小关键字的结点
从根表中找到最小关键字的结点，将以该结点为根的整棵二项树从堆取出，删除取出的二项树的根，将其剩下的子女倒序排列，组成了一个新的二项堆，再与之前的二项堆合并。??
?
//抽取有最小关键字的结点BinHeap BinHeapExtractMin(BinHeap &heap) { BinHeap pre_y = NULL, y = NULL, x = heap; int min = INT_MAX; while (x != NULL) { if (x->key < min) { min = x->key; pre_y = y; y = x; } x = x->sibling; } if (y == NULL) { return NULL; } if (pre_y == NULL) { heap = heap->sibling; } else { pre_y->sibling = y->sibling; } //将y的子结点指针reverse BinHeap H2 = NULL, p = NULL; x = y->leftChild; while (x != NULL) { p = x; x = x->sibling; p->sibling = H2; H2 = p; p->parent = NULL; } heap = BinHeapUnion(heap, H2); return y;}
?
?6）减小关键字的值
减小关键字的值其实就是更新关键字的值，实现过程就是维护最小堆的过程。
?
//减少关键字的值void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key) { if(key > x->key) { puts("new key is greaer than current key"); exit(1); //不为降键 } x->key = key; BinHeap z = NULL, y = NULL; y = x; z = x->parent; while(z != NULL && z->key > y->key) { swap(z->key, y->key); y = z; z = y->parent; }}
?
7）删除一个关键字
删除一个关键字转换为前面的过程——将该关键字修改为最小值（要维护最小堆的性质），然后变成删除最小关键字的过程。?
?
//删除一个关键字BinHeap BinHeapDelete(BinHeap &heap, int key) { BinHeap x = NULL; x = BinHeapFind(heap, key); if (x != NULL) { BinHeapDecreaseKey(heap, x, INT_MIN); return BinHeapExtractMin(heap); } return x;} //找出一个关键字BinHeap BinHeapFind(BinHeap &heap, int key) { Position p = NULL, x = NULL; p = heap; while (p != NULL) { if (p->key == key) { return p; } else { if((x =BinHeapFind(p->leftChild, key)) != NULL) { return x; } p = p->sibling; } } return NULL;}
??
二项树的完整实现
?
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<climits>using namespace std; typedef struct BinHeapNode BinNode;typedef struct BinHeapNode * BinHeap;typedef struct BinHeapNode * Position; //结点ADTstruct BinHeapNode { int key; int degree; Position parent; Position leftChild; Position sibling;}; //用数组内的值建堆BinHeap MakeBinHeapWithArray(int keys[], int n); //两个堆合并BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2); //将H1, H2的根表合并成一个按度数的单调递增次序排列的链表BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2); //使H2成为H1的父节点void BinLink(BinHeap &H1, BinHeap &H2); //返回最小根节点的指针BinHeap BinHeapMin(BinHeap heap); //减少关键字的值void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key); //删除一个关键字BinHeap BinHeapDelete(BinHeap &heap, int key); //找出一个关键字BinHeap BinHeapFind(BinHeap &heap, int key); //打印输出堆结构void PrintBinHeap(BinHeap heap); //销毁堆void DestroyBinHeap(BinHeap &heap); //用数组内的值建堆BinHeap MakeBinHeapWithArray(int keys[], int n) { BinHeap heap = NULL, newHeap = NULL; for (int i = 0; i < n; i++) { newHeap = (BinHeap) malloc(sizeof(BinNode)); if (newHeap == NULL) { puts("Out of the Space"); exit(1); } memset(newHeap, 0, sizeof(BinNode)); newHeap->key = keys[i]; if (NULL == heap) { heap = newHeap; } else { heap = BinHeapUnion(heap, newHeap); newHeap = NULL; } } return heap;} //两个堆合并BinHeap BinHeapUnion(BinHeap &H1, BinHeap &H2) { Position heap = NULL, pre_x = NULL, x = NULL, next_x = NULL; heap = BinHeapMerge(H1, H2); if (heap == NULL) { return heap; } pre_x = NULL; x = heap; next_x = x->sibling; while (next_x != NULL) { if ((x->degree != next_x->degree) ||//Cases 1 and 2 ((next_x->sibling != NULL) && (next_x->degree == next_x->sibling->degree))) { pre_x = x; x = next_x; } else if (x->key <= next_x->key) {//Cases 3 x->sibling = next_x->sibling; BinLink(next_x, x); } else {//Cases 4 if (pre_x == NULL) { heap = next_x; } else { pre_x->sibling = next_x; } BinLink(x, next_x); x = next_x; } next_x = x->sibling; } return heap;} //将H1, H2的根表合并成一个按度数的单调递增次序排列的链表BinHeap BinHeapMerge(BinHeap &H1, BinHeap &H2) { //heap->堆的首地址，H3为指向新堆根结点 BinHeap heap = NULL, firstHeap = NULL, secondHeap = NULL, pre_H3 = NULL, H3 = NULL; if (H1 != NULL && H2 != NULL){ firstHeap = H1; secondHeap = H2; //整个while，firstHeap, secondHeap, pre_H3, H3都在往后顺移 while (firstHeap != NULL && secondHeap != NULL) { if (firstHeap->degree <= secondHeap->degree) { H3 = firstHeap; firstHeap = firstHeap->sibling; } else { H3 = secondHeap; secondHeap = secondHeap->sibling; } if (pre_H3 == NULL) { pre_H3 = H3; heap = H3; } else { pre_H3->sibling = H3; pre_H3 = H3; } if (firstHeap != NULL) { H3->sibling = firstHeap; } else { H3->sibling = secondHeap; } }//while } else if (H1 != NULL) { heap = H1; } else { heap = H2; } H1 = H2 = NULL; return heap;} //使H2成为H1的父节点void BinLink(BinHeap &H1, BinHeap &H2) { H1->parent = H2; H1->sibling = H2->leftChild; H2->leftChild = H1; H2->degree++;} //返回最小根节点的指针BinHeap BinHeapMin(BinHeap heap) { Position y = NULL, x = heap; int min = INT_MAX; while (x != NULL) { if (x->key < min) { min = x->key; y = x; } x = x->sibling; } return y;} //抽取有最小关键字的结点BinHeap BinHeapExtractMin(BinHeap &heap) { BinHeap pre_y = NULL, y = NULL, x = heap; int min = INT_MAX; while (x != NULL) { if (x->key < min) { min = x->key; pre_y = y; y = x; } x = x->sibling; } if (y == NULL) { return NULL; } if (pre_y == NULL) { heap = heap->sibling; } else { pre_y->sibling = y->sibling; } //将y的子结点指针reverse BinHeap H2 = NULL, p = NULL; x = y->leftChild; while (x != NULL) { p = x; x = x->sibling; p->sibling = H2; H2 = p; p->parent = NULL; } heap = BinHeapUnion(heap, H2); return y;} //减少关键字的值void BinHeapDecreaseKey(BinHeap heap, BinHeap x, int key) { if(key > x->key) { puts("new key is greaer than current key"); exit(1); //不为降键 } x->key = key; BinHeap z = NULL, y = NULL; y = x; z = x->parent; while(z != NULL && z->key > y->key) { swap(z->key, y->key); y = z; z = y->parent; }} //删除一个关键字BinHeap BinHeapDelete(BinHeap &heap, int key) { BinHeap x = NULL; x = BinHeapFind(heap, key); if (x != NULL) { BinHeapDecreaseKey(heap, x, INT_MIN); return BinHeapExtractMin(heap); } return x;} //找出一个关键字BinHeap BinHeapFind(BinHeap &heap, int key) { Position p = NULL, x = NULL; p = heap; while (p != NULL) { if (p->key == key) { return p; } else { if((x =BinHeapFind(p->leftChild, key)) != NULL) { return x; } p = p->sibling; } } return NULL;} //打印输出堆结构void PrintBinHeap(BinHeap heap) { if (NULL == heap) { return ; } Position p = heap; while (p != NULL) { printf(" ("); printf("%d", p->key); //显示其孩子 if(NULL != p->leftChild) { PrintBinHeap(p->leftChild); } printf(") "); p = p->sibling; }} int kp1[8] = {12, 7, 25, 15, 28, 33, 41}; int kp2[20] = {18, 3, 37, 6, 8, 29, 10, 44, 30, 23, 2, 48, 31, 17, 45, 32, 24, 50, 55}; int kp4[23] = {37, 41, 10, 28, 13, 77, 1, 6, 16, 12, 25, 8, 14, 29, 26, 23, 18, 11, 17, 38, 42, 27};int main() { BinHeap H1 = NULL; H1 = MakeBinHeapWithArray(kp1, 7); puts("第一个二叉堆H1:"); PrintBinHeap(H1); BinHeap H2 = NULL; H2 = MakeBinHeapWithArray(kp2, 19); puts("\n\n第二个二叉堆H2:"); PrintBinHeap(H2); BinHeap H3 = NULL; H3 = BinHeapUnion(H1, H2); puts("\n\n合并H1,H2后，得到H3:"); PrintBinHeap(H3); BinHeap H4 = NULL; H4 = MakeBinHeapWithArray(kp4, 22); puts("\n\n用于测试提取和删除的二叉堆H4:"); PrintBinHeap(H4); BinHeap extractNode = BinHeapExtractMin(H4); if (extractNode != NULL) { printf("\n\n抽取最小的值%d后：\n", extractNode->key); PrintBinHeap(H4); } extractNode = BinHeapExtractMin(H4); if (extractNode != NULL) { printf("\n\n抽取最小的值%d后：\n", extractNode->key); PrintBinHeap(H4); } extractNode = BinHeapExtractMin(H4); if (extractNode != NULL) { printf("\n\n抽取最小的值%d后：\n", extractNode->key); PrintBinHeap(H4); } BinHeapDelete(H4, 12); puts("\n\n删除12后："); PrintBinHeap(H4); return 0;}
?
另外的实现参考参考②。
上述的操作的时间复杂度都是O(lgn)。?
?
斐波那契堆（Fibonacci Heap）
斐波那契堆是一种松散的二项堆，与二项堆的主要区别在于构成斐波那契堆得树可以不是二项树，并且这些树的根排列是无须的（二项堆的根结点排序是按照结点个数排序的，不是按照根结点的大小）。斐波那契堆得优势在于它对建堆、插入、抽取最小关键字、联合等操作能在O(1)的时间内完成（不涉及删除元素的操作仅需要O（1））。这是对二项堆效率的巨大改善。但由于斐波那契堆得常数因子以及程序设计上的复杂度，使它不如通常的二叉堆合适。因此，它的价值仅存在于理论意义上。斐波那契堆的另一个特点就是合并操作只发生在抽取一个结点之后，也就是说斐波那契堆的维护总是会延后的（个人根据代码理解的）。
斐波那契堆结点ADT
结点含有以下域：
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]——标记是否失去了一个孩子
?
//斐波那契结点ADTstruct FibonacciHeapNode { int key; //结点 int degree; //度 FibonacciHeapNode * left; //左兄弟 FibonacciHeapNode * right; //右兄弟 FibonacciHeapNode * parent; //父结点 FibonacciHeapNode * child; //第一个孩子结点 bool marked; //是否被删除第1个孩子};typedef FibonacciHeapNode FibNode;
?
斐波那契堆ADT
对于一个给定的斐波那契堆H，可以通过指向包含最小关键字的树根的指针min[H]来访问，这个结点被称为斐波那契堆中的最小结点。如果一个斐波那契堆H是空的，则min[H] = NIL. 在一个斐波那契堆中，所有树的根都通过left和right指针链接成一个环形的双链表，称为堆的根表。于是，指针min[H]就指向根表中具有最小关键字的结点（就是查找最小结点的操作，下文就没有再介绍了）。
//斐波那契堆ADTstruct FibonacciHeap { int keyNum; //堆中结点个数 FibonacciHeapNode * min;//最小堆，根结点 int maxNumOfDegree; //最大度 FibonacciHeapNode * * cons;//指向最大度的内存区域}; typedef FibonacciHeap FibHeap;
斐波那契堆操作
1.创建斐波那契堆
创建一个空的斐波那契堆，过程MAKE-FIB-HEAP 分配并返回一个斐波那契堆对象H；?
?
//初始化一个空的Fibonacci HeapFibHeap * 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;} //初始化结点xFibNode * 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;}
?
2.插入一个结点
要出人一个结点x，对结点的各域初始化，赋值，然后构造自身的环形双向链表后，将x加入H的根表中。也就是说，结点x 成为一棵单结点的最小堆有序树，同时就是斐波那契堆中一棵无序树而且在根表最小结点的左边。
? ? ?如图是将关键字为21的结点插入斐波那契堆。该结点自成一棵最小堆有序树，从而被加入到根表中，成为根的左兄弟。?
?
?
//堆结点x插入fibonacci heap中void FibHeapInsert(FibHeap * heap, FibNode * x) { if (0 == heap->keyNum) { heap->min = x; } else { FibNodeAdd(x, heap->min); x->parent = NULL; if (x->key < heap->min->key) { heap->min = x; } } heap->keyNum++;} //将数组内的值插入Fibonacci Heapvoid FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum) { for (int i = 0; i < keyNum; i++) { FibHeapInsertKey(heap, keys[i]); }} //将值插入Fibonacci Heapstatic void FibHeapInsertKey(FibHeap * heap, int key) { FibNode * x = NULL; x = FibHeapNodeMake(); x->key = key; FibHeapInsert(heap, x);}
?
3.合并两个堆
不同于二项堆，这个操作在斐波那契堆里非常简单。仅仅简单地将H1和H2的两根表串联，然后确定一个新的最小结点。
4.抽取（删除）最小结点
抽取最小结点的操作是斐波那契堆最复杂的操作，就是过程比较多，下面一步一步介绍。
1）将要抽取最小结点的子树都直接串联在根表中，如图（b）
2）然后就是合并所有degree相等的树，直到没有相等的degree的树。
（1）先定义一个数组A，数组A保存的根表子树中的头结点，A[i]=y表示树 y 的degree值是 i 。这样就可以得到数组A的长度就等于当前斐波那契堆中degree的最大值。
（2）当发现两个相等的degree的树，就执行合并操作。“发现”是这样得到的——向右遍历根表的结点，得到当前子树的degree的值，如果该degree值在A数组已经有元素则就是degree相等，就可以合并了。如图（e）（f）就是将degree等于 1的两个子树合并。
?
?
//抽取最小结点FibNode * FibHeapExtractMin(FibHeap * heap) { FibNode * x = NULL, * z = heap->min; if (z != NULL) { //删除z的每一个孩子 while (NULL != z->child) { x = z->child; FibNodeRemove(x); if (x->right == x) { z->child = NULL; } else { z->child = x->right; } FibNodeAdd(x, z);//add x to the root list heap x->parent = NULL; } FibNodeRemove(z); if (z->right == z) { heap->min = NULL; } else { heap->min = z->right; FibHeapConsolidate(heap); } heap->keyNum--; } return z;} //合并左右相同度数的二项树void FibHeapConsolidate(FibHeap * heap) { int D, d; FibNode * w = heap->min, * x = NULL, * y = NULL; FibHeapConsMake(heap);//开辟哈希所用空间 D = heap->maxNumOfDegree + 1; for (int i = 0; i < D; i++) { *(heap->cons + i) = NULL; } //合并相同度的根节点，使每个度数的二项树唯一 while (NULL != heap->min) { x = FibHeapMinRemove(heap); d = x->degree; while (NULL != *(heap->cons + d)) { y = *(heap->cons + d); if (x->key > y->key) {//根结点key最小 swap(x, y); } FibHeapLink(heap, y, x); *(heap->cons + d) = NULL; d++; } *(heap->cons + d) = x; } heap->min = NULL;//原有根表清除 //将heap->cons中结点都重新加到根表中，且找出最小根 for (int i = 0; i < D; i++) { if (*(heap->cons + i) != NULL) { if (NULL == heap->min) { heap->min = *(heap->cons + i); } else { FibNodeAdd(*(heap->cons + i), heap->min); if ((*(heap->cons + i))->key < heap->min->key) { heap->min = *(heap->cons + i); }//if(<) }//if-else(==) }//if(!=) }//for(i)} //将x根结点链接到y根结点void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y) { FibNodeRemove(x); if (NULL == y->child) { y->child = x; } else { FibNodeAdd(x, y->child); } x->parent = y; y->degree++; x->marked = false;} //开辟FibHeapConsolidate函数哈希所用空间static void FibHeapConsMake(FibHeap * heap) { int old = heap->maxNumOfDegree; heap->maxNumOfDegree = int(log(heap->keyNum * 1.0) / log(2.0)) + 1; if (old < heap->maxNumOfDegree) { //因为度为heap->maxNumOfDegree可能被合并,所以要maxNumOfDegree + 1 heap->cons = (FibNode **) realloc(heap->cons, sizeof(FibHeap *) * (heap->maxNumOfDegree + 1)); if (NULL == heap->cons) { puts("Out of Space!"); exit(1); } }} //将堆的最小结点移出，并指向其有兄弟static FibNode *FibHeapMinRemove(FibHeap * heap) { FibNode *min = heap->min; if (heap->min == min->right) { heap->min = NULL; } else { FibNodeRemove(min); heap->min = min->right; } min->left = min->right = min; return min;}
??
5.减小一个关键字
减小一个关键字的字，会破坏最小堆的性质，所以要进行最小堆维护。因为斐波那契支持减小关键字和删除结点操作，所以斐波那契堆的子树就不一定是二项树了。
减小一个关键字主要进行两个步骤：
1）减小关键字，如果破坏最小堆性质，则将该结点a直接从原来的树移除直接串联在根表中，并将父结点p的mark属性设置成长true。
2）进行级联剪枝：如果当前父结点p的mark属性是true，且p的父结点pp的mark属性也是true，那么将p从pp移除加入到根表中
下图中，黑色的结点表示其mark属性为true，(a)(b)将关键字46减少为15，没有发生级联剪枝；（c,d,e）将35减小为5，发生了级联剪枝操作
//减小一个关键字void FibHeapDecrease(FibHeap * heap, FibNode * x, int key) { FibNode * y = x->parent; if (x->key < key) { puts("new key is greater than current key!"); exit(1); } x->key = key; if (NULL != y && x->key < y->key) { //破坏了最小堆性质，需要进行级联剪切操作 FibHeapCut(heap, x, y); FibHeapCascadingCut(heap, y); } if (x->key < heap->min->key) { heap->min = x; }} //切断x与父节点y之间的链接，使x成为一个根static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y) { FibNodeRemove(x); renewDegree(y, x->degree); if (x == x->right) { y->child = NULL; } else { y->child = x->right; } x->parent = NULL; x->left = x->right = x; x->marked = false; FibNodeAdd(x, heap->min);} //级联剪切static void FibHeapCascadingCut(FibHeap * heap, FibNode * y) { FibNode * z = y->parent; if (NULL != z) { if (y->marked == false) { y->marked = true; } else { FibHeapCut(heap, y, z); FibHeapCascadingCut(heap, z); } }} //修改度数void renewDegree(FibNode * parent, int degree) { parent->degree -= degree; if (parent-> parent != NULL) { renewDegree(parent->parent, degree); }}
?6.删除一个结点
删除结点X，首先将X的关键字值减小到比最小结点的值更小（调用减小一个关键字的过程），然后删除（抽取）最小结点就可以了。
//删除结点void FibHeapDelete(FibHeap * heap, FibNode * x) { FibHeapDecrease(heap, x, INT_MIN); FibHeapExtractMin(heap);}
?
斐波那契堆完整实现
?
//说明：//代码中Fibonacci Heap 用变量heap表示//结点通常用x，y等表示#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<climits>using namespace std; //斐波那契结点ADTstruct FibonacciHeapNode { int key; //结点 int degree; //度 FibonacciHeapNode * left; //左兄弟 FibonacciHeapNode * right; //右兄弟 FibonacciHeapNode * parent; //父结点 FibonacciHeapNode * child; //第一个孩子结点 bool marked; //是否被删除第1个孩子}; typedef FibonacciHeapNode FibNode; //斐波那契堆ADTstruct FibonacciHeap { int keyNum; //堆中结点个数 FibonacciHeapNode * min;//最小堆，根结点 int maxNumOfDegree; //最大度 FibonacciHeapNode * * cons;//指向最大度的内存区域}; typedef FibonacciHeap FibHeap; /*****************函数申明*************************///将x从双链表移除inline void FibNodeRemove(FibNode * x); //将x堆结点加入y结点之前(循环链表中)void FibNodeAdd(FibNode * x, FibNode * y); //初始化一个空的Fibonacci HeapFibHeap * FibHeapMake() ; //初始化结点xFibNode * FibHeapNodeMake(); //堆结点x插入fibonacci heap中void FibHeapInsert(FibHeap * heap, FibNode * x); //将数组内的值插入Fibonacci Heapvoid FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum); //将值插入Fibonacci Heapstatic void FibHeapInsertKey(FibHeap * heap, int key); //抽取最小结点FibNode * FibHeapExtractMin(FibHeap * heap); //合并左右相同度数的二项树void FibHeapConsolidate(FibHeap * heap); //将x根结点链接到y根结点void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y); //开辟FibHeapConsolidate函数哈希所用空间static void FibHeapConsMake(FibHeap * heap); //将堆的最小结点移出，并指向其有兄弟static FibNode *FibHeapMinRemove(FibHeap * heap); //减小一个关键字void FibHeapDecrease(FibHeap * heap, FibNode * x, int key); //切断x与父节点y之间的链接，使x成为一个根static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y); //级联剪切static void FibHeapCascadingCut(FibHeap * heap, FibNode * y); //修改度数void renewDegree(FibNode * parent, int degree); //删除结点void FibHeapDelete(FibHeap * heap, FibNode * x); //堆内搜索关键字FibNode * FibHeapSearch(FibHeap * heap, int key); //被FibHeapSearch调用static FibNode * FibNodeSearch(FibNode * x, int key); //销毁堆void FibHeapDestory(FibHeap * heap); //被FibHeapDestory调用static void FibNodeDestory(FibNode * x); //输出打印堆static void FibHeapPrint(FibHeap * heap); //被FibHeapPrint调用static void FibNodePrint(FibNode * x);/************************************************/ //将x从双链表移除inline void FibNodeRemove(FibNode * x) { x->left->right = x->right; x->right->left = x->left;} /*将x堆结点加入y结点之前(循环链表中) a …… y a …… x …… y*/inline void FibNodeAdd(FibNode * x, FibNode * y) { x->left = y->left; y->left->right = x; x->right = y; y->left = x;} //初始化一个空的Fibonacci HeapFibHeap * 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;} //初始化结点xFibNode * 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;} //堆结点x插入fibonacci heap中void FibHeapInsert(FibHeap * heap, FibNode * x) { if (0 == heap->keyNum) { heap->min = x; } else { FibNodeAdd(x, heap->min); x->parent = NULL; if (x->key < heap->min->key) { heap->min = x; } } heap->keyNum++;} //将数组内的值插入Fibonacci Heapvoid FibHeapInsertKeys(FibHeap * heap, int keys[], int keyNum) { for (int i = 0; i < keyNum; i++) { FibHeapInsertKey(heap, keys[i]); }} //将值插入Fibonacci Heapstatic void FibHeapInsertKey(FibHeap * heap, int key) { FibNode * x = NULL; x = FibHeapNodeMake(); x->key = key; FibHeapInsert(heap, x);} //抽取最小结点FibNode * FibHeapExtractMin(FibHeap * heap) { FibNode * x = NULL, * z = heap->min; if (z != NULL) { //删除z的每一个孩子 while (NULL != z->child) { x = z->child; FibNodeRemove(x); if (x->right == x) { z->child = NULL; } else { z->child = x->right; } FibNodeAdd(x, z);//add x to the root list heap x->parent = NULL; } FibNodeRemove(z); if (z->right == z) { heap->min = NULL; } else { heap->min = z->right; FibHeapConsolidate(heap); } heap->keyNum--; } return z;} //合并左右相同度数的二项树void FibHeapConsolidate(FibHeap * heap) { int D, d; FibNode * w = heap->min, * x = NULL, * y = NULL; FibHeapConsMake(heap);//开辟哈希所用空间 D = heap->maxNumOfDegree + 1; for (int i = 0; i < D; i++) { *(heap->cons + i) = NULL; } //合并相同度的根节点，使每个度数的二项树唯一 while (NULL != heap->min) { x = FibHeapMinRemove(heap); d = x->degree; while (NULL != *(heap->cons + d)) { y = *(heap->cons + d); if (x->key > y->key) {//根结点key最小 swap(x, y); } FibHeapLink(heap, y, x); *(heap->cons + d) = NULL; d++; } *(heap->cons + d) = x; } heap->min = NULL;//原有根表清除 //将heap->cons中结点都重新加到根表中，且找出最小根 for (int i = 0; i < D; i++) { if (*(heap->cons + i) != NULL) { if (NULL == heap->min) { heap->min = *(heap->cons + i); } else { FibNodeAdd(*(heap->cons + i), heap->min); if ((*(heap->cons + i))->key < heap->min->key) { heap->min = *(heap->cons + i); }//if(<) }//if-else(==) }//if(!=) }//for(i)} //将x根结点链接到y根结点void FibHeapLink(FibHeap * heap, FibNode * x, FibNode *y) { FibNodeRemove(x); if (NULL == y->child) { y->child = x; } else { FibNodeAdd(x, y->child); } x->parent = y; y->degree++; x->marked = false;} //开辟FibHeapConsolidate函数哈希所用空间static void FibHeapConsMake(FibHeap * heap) { int old = heap->maxNumOfDegree; heap->maxNumOfDegree = int(log(heap->keyNum * 1.0) / log(2.0)) + 1; if (old < heap->maxNumOfDegree) { //因为度为heap->maxNumOfDegree可能被合并,所以要maxNumOfDegree + 1 heap->cons = (FibNode **) realloc(heap->cons, sizeof(FibHeap *) * (heap->maxNumOfDegree + 1)); if (NULL == heap->cons) { puts("Out of Space!"); exit(1); } }} //将堆的最小结点移出，并指向其有兄弟static FibNode *FibHeapMinRemove(FibHeap * heap) { FibNode *min = heap->min; if (heap->min == min->right) { heap->min = NULL; } else { FibNodeRemove(min); heap->min = min->right; } min->left = min->right = min; return min;} //减小一个关键字void FibHeapDecrease(FibHeap * heap, FibNode * x, int key) { FibNode * y = x->parent; if (x->key < key) { puts("new key is greater than current key!"); exit(1); } x->key = key; if (NULL != y && x->key < y->key) { //破坏了最小堆性质，需要进行级联剪切操作 FibHeapCut(heap, x, y); FibHeapCascadingCut(heap, y); } if (x->key < heap->min->key) { heap->min = x; }} //切断x与父节点y之间的链接，使x成为一个根static void FibHeapCut(FibHeap * heap, FibNode * x, FibNode * y) { FibNodeRemove(x); renewDegree(y, x->degree); if (x == x->right) { y->child = NULL; } else { y->child = x->right; } x->parent = NULL; x->left = x->right = x; x->marked = false; FibNodeAdd(x, heap->min);} //级联剪切static void FibHeapCascadingCut(FibHeap * heap, FibNode * y) { FibNode * z = y->parent; if (NULL != z) { if (y->marked == false) { y->marked = true; } else { FibHeapCut(heap, y, z); FibHeapCascadingCut(heap, z); } }} //修改度数void renewDegree(FibNode * parent, int degree) { parent->degree -= degree; if (parent-> parent != NULL) { renewDegree(parent->parent, degree); }} //删除结点void FibHeapDelete(FibHeap * heap, FibNode * x) { FibHeapDecrease(heap, x, INT_MIN); FibHeapExtractMin(heap);} //堆内搜索关键字FibNode * FibHeapSearch(FibHeap * heap, int key) { return FibNodeSearch(heap->min, key);} //被FibHeapSearch调用static FibNode * FibNodeSearch(FibNode * x, int key) { FibNode * w = x, * y = NULL; if (x != NULL) { do { if (w->key == key) { y = w; break; } else if (NULL != (y = FibNodeSearch(w->child, key))) { break; } w = w->right; } while (w != x); } return y;} //销毁堆void FibHeapDestory(FibHeap * heap) { FibNodeDestory(heap->min); free(heap); heap = NULL;} //被FibHeapDestory调用static void FibNodeDestory(FibNode * x) { FibNode * p = x, *q = NULL; while (p != NULL) { FibNodeDestory(p->child); q = p; if (p -> left == x) { p = NULL; } else { p = p->left; } free(q->right); }} //输出打印堆static void FibHeapPrint(FibHeap * heap) { printf("The keyNum = %d\n", heap->keyNum); FibNodePrint(heap->min); puts("\n");}; //被FibHeapPrint调用static void FibNodePrint(FibNode * x) { FibNode * p = NULL; if (NULL == x) { return ; } p = x; do { printf(" ("); printf("%d", p->key); if (p->child != NULL) { FibNodePrint(p->child); } printf(") "); p = p->left; }while (x != p);} int keys[10] = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11}; int main() { FibHeap * heap = NULL; FibNode * x = NULL; heap = FibHeapMake(); FibHeapInsertKeys(heap, keys, 10); FibHeapPrint(heap); x = FibHeapExtractMin(heap); printf("抽取最小值%d之后：\n", x->key); FibHeapPrint(heap); x = FibHeapSearch(heap, 11); if (NULL != x) { printf("查找%d成功,", x->key); FibHeapDecrease(heap, x, 8); printf("减小到%d后：\n", x->key); FibHeapPrint(heap); } x = FibHeapSearch(heap, 7); if (NULL != x) { printf("删除%d成功:\n", x->key); FibHeapDelete(heap, x); FibHeapPrint(heap); } FibHeapDestory(heap); return 0;}
?
Pairing Heap
斐波那契堆主要有两个缺点：编程实现难度较大和实际效率没有理论的那么快（由于它的存储结构和四个指针）。Pairing Heap的提出就是弥补斐波那契堆的两个缺点——编程简单操作的时间复杂度和斐波那契堆一样。
Pairing Heap其实就是一个具有堆（最大堆或最小堆）性质的树，它的特性不是由它的结构决定的，而是由于它的操作（插入，合并，减小一个关键字等）决定的。
?
Pairing Heap的ADT
?
typedef struct PairingHeapNode{intkey;structPairingHeapNode*child;structPairingHeapNode*sibling;structPairingHeapNode*prev;}PairHeap;
?
Pairing Heap 的操作
注意：图解过程是以最大堆来演示的，但是代码是以最小堆来写的，见谅！
1.合并两个子堆

static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q){if(q == NULL)return p;else if(p->key <= q->key){q->prev = p;p->sibling = q->sibling;if(p->sibling != NULL)p->sibling->prev = p;q->sibling = p->child;if(q->sibling != NULL)q->sibling->prev = q;p->child = q;return p;}else{q->prev = p->prev;p->prev = q;p->sibling = q->child;if(p->sibling != NULL)p->sibling->prev = p;q->child = p;return q;}}
??
2. 插入一个结点

PairHeap* PairHeap_insert(PairHeap *p, int key){PairHeap *node;node = (PairHeap*)malloc(sizeof(*node));if(node == NULL)return NULL;node->key = key;node->child = node->sibling = node->prev = NULL;if(p == NULL)return node;elsereturn merge_subheaps(p, node);}
3.增加（减小）一个关键字

?

PairHeap* PairHeap_DecreaseKey(PairHeap *p, PairHeap *pos, int d){if(d < 0)return p;pos->key = pos->key - d;if(p == pos)return p;if(pos->sibling != NULL)pos->sibling->prev = pos->prev;if(pos->prev->child = pos)pos->prev->child = pos->sibling;elsepos->prev->sibling = p->sibling;p->sibling = NULL;return merge_subheaps(p, pos);}?
5.删除最小结点

?
?
Pairing Heap完整实现
?
#include <stdlib.h>typedef struct PairingHeapNode{intkey;structPairingHeapNode*child;structPairingHeapNode*sibling;structPairingHeapNode*prev;}PairHeap;static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q);static PairHeap* combine_siblings(PairHeap *p);PairHeap* PairHeap_insert(PairHeap *p, int key){PairHeap *node;node = (PairHeap*)malloc(sizeof(*node));if(node == NULL)return NULL;node->key = key;node->child = node->sibling = node->prev = NULL;if(p == NULL)return node;elsereturn merge_subheaps(p, node);}PairHeap* PairHeap_DecreaseKey(PairHeap *p, PairHeap *pos, int d){if(d < 0)return p;pos->key = pos->key - d;if(p == pos)return p;if(pos->sibling != NULL)pos->sibling->prev = pos->prev;if(pos->prev->child = pos)pos->prev->child = pos->sibling;elsepos->prev->sibling = p->sibling;p->sibling = NULL;return merge_subheaps(p, pos);}PairHeap* PairHeap_DeleteMin(int *key, PairHeap *p){PairHeap *new_root;if(p == NULL)return NULL;else{*key = p->key;if(p->child != NULL)new_root = combine_siblings(p->child);free(p);}return new_root;}static PairHeap* combine_siblings(PairHeap *p){PairHeap *tree_array[1024];int i, count;if(p->sibling == NULL)return p;for(count = 0; p != NULL; count++){tree_array[count] = p;p->prev->sibling = NULL;p = p->sibling;}tree_array[count] = NULL;for(i = 1; i < count; i++)tree_array[i] = merge_subheaps(tree_array[i-1], tree_array[i]);return tree_array[count-1];}static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q){if(q == NULL)return p;else if(p->key <= q->key){q->prev = p;p->sibling = q->sibling;if(p->sibling != NULL)p->sibling->prev = p;q->sibling = p->child;if(q->sibling != NULL)q->sibling->prev = q;p->child = q;return p;}else{q->prev = p->prev;p->prev = q;p->sibling = q->child;if(p->sibling != NULL)p->sibling->prev = p;q->child = p;return q;}}
??
小结
终于到小结了，这篇文章写得比较吃力，如斐波那契堆的“减小一个关键字”的操作我就对使用级联剪切还没有找到解释，还有还没有找到Pairing Heap的定义，唯独只有自己理解和揣测（比如pairing heap没有明确的定义，本人个人理解pairing heap的独特性一定在他的操作，即行为决定特征）但总归还是相对完整，希望能对你有说帮助。如果你有任何建议、批评或补充，还请你不吝提出，不甚感激。更多参考请移步互联网。
?
?
?
?
参考：
①酷~行天下：http://mindlee.net/2011/09/26/binomial-heaps/
②Bj?rn B. Brandenburg：http://www.cs.unc.edu/~bbb/#binomial_heaps
③酷~行天下：http://mindlee.net/2011/09/29/fibonacci-heaps/
④Adoo's blog?：http://www.roading.org/algorithm/introductiontoalgorithm/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E5%A0%86fibonacci-heaps.html
⑤Golden_Shadow：http://blog.csdn.net/golden_shadow/article/details/6216921
⑥Sartaj Sahni：http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm
⑦C++ template Fibonacci heap, with demonstration：http://ideone.com/9jYnv
⑧"The pairing heap: a new form of self-adjusting heap"：http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/pairing-heaps.pdf
⑨Vikas Tandi?：http://programmingpraxis.com/2009/08/14/pairing-heaps/
⑩http://www.cise.ufl.edu/~sahni/cop5536/slides/lec156.pdf
⑩+1：算法导论和维基百科
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1 楼 cometzb_xujun 2012-11-03 厉害！！厉害 2 楼 DSQiu 2012-11-03 cometzb_xujun 写道厉害！！厉害
谢谢你的鼓励，我会继续努力，争取写得更好…… 3 楼 max117 2012-11-03 支持楼主写下去，这才是纯技术流文章。
楼主的排版跟代码都很清晰，这一点很不容易。 4 楼 javaboy8282 2012-11-03 让咱这数学不好的情以何堪哇不过楼主真的很强大顶了 5 楼 DSQiu 2012-11-03 javaboy8282 写道让咱这数学不好的情以何堪哇不过楼主真的很强大顶了
谢谢，加油…… 6 楼 DSQiu 2012-11-03 max117 写道支持楼主写下去，这才是纯技术流文章。
楼主的排版跟代码都很清晰，这一点很不容易。
嗯，谢谢，突然发现@max117真懂我…… 7 楼 jiang_918 前天支持！支持！ 8 楼 DSQiu 前天 jiang_918 写道支持！支持！
谢谢，更多惊喜，敬请期待…… 9 楼 lection.yu 前天辛苦了。那些人脸皮太厚了。 10 楼 DSQiu 前天 lection.yu 写道辛苦了。那些人脸皮太厚了。
嗯嗯，谢谢…… 11 楼 guji528 前天支持原创。写文章都很累了，还是去防备自己写的东西被别人占用、更累了。 12 楼 DSQiu 前天 guji528 写道支持原创。写文章都很累了，还是去防备自己写的东西被别人占用、更累了。
是呀，每写一篇文章都要话费很大的心思和精力……}

优先队列3大利器二项堆、斐波那契

热点推荐