斐波拉契堆是由一组最小堆有序树组成，每棵树遵循最小堆性质，，并且每棵树都是有根而无序的。所有树的根通过left和right指针来形成一个环形的双链表，称为该堆的根表。
对于一个给定的斐波拉契堆H ，可以通过指向包含最小关键字的树根指针H.min来访问。堆中每个节点还包含x.mark,x.degree两个域，x.degree表示x的子女表中的子女个数；x.mark表示从x上次成为另一个节点子女以来是否失掉一个孩子。
斐波拉契对的结构如下：
势能函数：
可以利用势能方法来分析斐波拉契堆的性能。其势能函数定义为：
其中m(H)指H中有标记节点的个数，t(H)表示H的根表中树的棵数。
最大度数：
假设在包含n个节点的斐波拉契堆中，节点的最大度数又一个已知的上界D(n),则有：
提取斐波拉契堆最小值代码如下：
#include<iostream>#include<cstdlib>using namespace std;typedef struct FibHeapNode{int key;int degree;FibHeapNode *left;FibHeapNode *right;FibHeapNode *parent;FibHeapNode *child;bool mark;FibHeapNode(int k):key(k),degree(0),left(NULL),right(NULL),parent(NULL),child(NULL),mark(false){}}FibHeapNode;typedef struct FibHeap{int Num; //the number of node in the heapFibHeapNode *min; //the minimum heap,root node//int maxDegree;//maximum degree}FibHeap;void AddNodeToRootList(FibHeapNode *Hmin,FibHeapNode *x){x->right = Hmin->right;x->left = Hmin ;if(Hmin->right !=NULL)Hmin->right->left = x;Hmin->right = x;}void FibHeap_Make(FibHeap *H){H->Num=0;H->min=NULL;//H->maxDegree=0;}void FibHeap_Insert(FibHeap *H,int k){FibHeapNode *x=new FibHeapNode(k);if(H->min==NULL)H->min=x;else{ AddNodeToRootList(H->min,x);if(x->key < H->min->key)H->min = x;}H->Num++;}void FibHeap_Create(FibHeap *H,int A[],int n){FibHeap_Make(H);for(int i=0;i<n;i++)FibHeap_Insert(H,A[i]);}int main(){int test_data[]={52,18,17,38,39,41,3,30,24,26,46,35,7,23};int n=sizeof(test_data)/sizeof(int);FibHeap *H=new FibHeap();FibHeap_Create(H,test_data,n);cout<<"Hmin="<<H->min->key<<endl;return 0;}运行结果如下：
【注：若有错误，请指正~~~~】
版权声明：本文为博主原创文章，未经博主允许不得转载。
对的，坚持;错的，放弃!
