斐波那契堆

斐波那契堆对一个集合支持以下操作：
（1）向集合插入一个元素（均摊复杂度log(n)）;
（2）集合最小值（O(1)）;
（3）删除最小值（O(log(n))）;
（4）两个斐波那契堆合并(均摊复杂度O(1)) ;
（5）将其中某个元素的值更改为另一个更小的值(均摊复杂度O(1));
（6）删除一个元素(log(n)).
  1 #include <cmath>
  2 #include <algorithm>
  3 #include <new>
  4 #include <assert.h>
  5 using namespace std;
  6 
  7 
  8 template<typename Type>
  9 class FibonacciHeap
 10 {
 11 public:
 12     typedef Type value_type;
 13     typedef Type& reference;
 14 private:
 15     struct FibonacciHeapNode
 16     {
 17         value_type key;
 18         int degree;
 19         FibonacciHeapNode* left;
 20         FibonacciHeapNode* right;
 21         FibonacciHeapNode* father;
 22         FibonacciHeapNode* son;
 23         bool marked;
 24 
 25         ~FibonacciHeapNode()
 26         {
 27             left=right=father=son=NULL;
 28         }
 29     };
 30 public:
 31     typedef FibonacciHeapNode* iterator;
 32 
 33 private:
 34     FibonacciHeapNode* m_MinNode;
 35     int m_NodeNumber;
 36     value_type m_MinValue;
 37     FibonacciHeapNode** m_ArrForConsolidate;
 38     int m_ArrForConsolidateSize;
 39 
 40     FibonacciHeapNode* newNode()
 41     {
 42         FibonacciHeapNode* node=new FibonacciHeapNode;
 43         node->left=NULL;
 44         node->right=NULL;
 45         node->father=NULL;
 46         node->son=NULL;
 47         node->marked=false;
 48         node->degree=0;
 49 
 50         return node;
 51     }
 52 
 53     /**
 54        将a插入b之前
 55     **/
 56     void insertNode(FibonacciHeapNode *a,FibonacciHeapNode*b)
 57     {
 58         a->left=b->left;
 59         b->left->right=a;
 60         a->right=b;
 61         b->left=a;
 62     }
 63 
 64     void linkHeap(FibonacciHeapNode* y,FibonacciHeapNode* x)
 65     {
 66         y->left->right=y->right;
 67         y->right->left=y->right;
 68         if(x->son==NULL)
 69         {
 70             x->son=y;
 71             y->left=y->right=y;
 72 
 73         }
 74         else
 75         {
 76             insertNode(y,x->son);
 77         }
 78         y->father=x;
 79         y->marked=false;
 80         x->degree++;
 81 
 82     }
 83 
 84     /***
 85        合并根链表 直到根链表上每一个根有不同的度数(degree)
 86     **/
 87     void consolidate()
 88     {
 89         int MAXDEGREE=int(log2(m_NodeNumber))*3;
 90         FibonacciHeapNode* cur=m_MinNode;
 91         int rootChainNodeNum=0;
 92         do
 93         {
 94             if(cur->degree>MAXDEGREE) MAXDEGREE=cur->degree;
 95             cur=cur->left;
 96             rootChainNodeNum++;
 97         }while(cur!=m_MinNode);
 98 
 99 
100         if(m_ArrForConsolidateSize<MAXDEGREE)
101         {
102             if(m_ArrForConsolidateSize) delete[] m_ArrForConsolidate;
103             m_ArrForConsolidateSize=MAXDEGREE*2+1;
104             m_ArrForConsolidate=new (std::nothrow)FibonacciHeapNode*[m_ArrForConsolidateSize];
105         }
106 
107 
108         for(int i=0;i<=MAXDEGREE;i++) m_ArrForConsolidate[i]=NULL;
109         cur=m_MinNode;
110         for(int i=0;i<rootChainNodeNum;i++)
111         {
112             FibonacciHeapNode* x=cur;
113             FibonacciHeapNode* next=cur->left;
114             int d=x->degree;
115             x->left=x->right=x;
116             while(m_ArrForConsolidate[d]!=NULL)
117             {
118                 FibonacciHeapNode* y=m_ArrForConsolidate[d];
119                 if(x->key>y->key)
120                 {
121                     FibonacciHeapNode* tmp=x;
122                     x=y;
123                     y=tmp;
124                 }
125                 linkHeap(y,x);
126                 m_ArrForConsolidate[d++]=NULL;
127             }
128             m_ArrForConsolidate[d]=x;
129             cur=next;
130         }
131 
132         m_MinNode=NULL;
133         for(int i=0;i<=MAXDEGREE;i++)
134         {
135             if(m_ArrForConsolidate[i]!=NULL)
136             {
137                 if(m_MinNode==NULL)
138                 {
139                     m_MinNode=m_ArrForConsolidate[i];
140                     m_MinNode->left=m_MinNode->right=m_MinNode;
141                 }
142                 else
143                 {
144                     insertNode(m_ArrForConsolidate[i],m_MinNode);
145                     if(m_ArrForConsolidate[i]->key<m_MinNode->key)
146                     {
147                         m_MinNode=m_ArrForConsolidate[i];
148                     }
149 
150                 }
151             }
152         }
153     }
154 
155     /**
156        x是y的儿子 切下x 并把x接入根链表
157     **/
158     void cut(FibonacciHeapNode*x,FibonacciHeapNode*y)
159     {
160         /**
161           y只有这个一个儿子
162         **/
163         if(x->left==x)
164         {
165             y->son=NULL;
166         }
167         else
168         {
169             x->left->right=x->right;
170             x->right->left=x->left;
171             if(y->son==x)
172             {
173                 y->son=x->left;
174             }
175         }
176         insertNode(x,m_MinNode);
177         x->father=NULL;
178         x->marked=false;
179         y->degree--;
180     }
181 
182     void cascadingCut(FibonacciHeapNode* y)
183     {
184         FibonacciHeapNode* z=y->father;
185         if(z!=NULL)
186         {
187             if(y->marked==false) y->marked=true;
188             else
189             {
190                 cut(y,z);
191                 cascadingCut(z);
192             }
193         }
194     }
195 
196     iterator search(FibonacciHeapNode* cur,const reference key)
197     {
198         if(cur==NULL) return NULL;
199 
200         FibonacciHeapNode* tmp=cur;
201         do
202         {
203             if(tmp->key==key) return tmp;
204             FibonacciHeapNode* ans=search(tmp->son,key);
205             if(ans) return ans;
206             tmp=tmp->left;
207         }while(tmp!=cur);
208         return NULL;
209     }
210 
211     void freeAll(FibonacciHeapNode* rt)
212     {
213         int sum=0;
214         FibonacciHeapNode* cur=rt;
215         do
216         {
217             sum++;
218             cur=cur->left;
219         }while(cur!=rt);
220         for(int i=0;i<sum;i++)
221         {
222             FibonacciHeapNode* next=cur->left;
223             if(cur->son) freeAll(cur->son);
224             delete cur;
225             cur=next;
226         }
227     }
228 
229 public:
230     FibonacciHeap(value_type MinValue):
231         m_MinNode(NULL),m_NodeNumber(0),m_MinValue(MinValue),m_ArrForConsolidateSize(0){}
232 
233     ~FibonacciHeap()
234     {
235         if(m_ArrForConsolidateSize>0) delete[] m_ArrForConsolidate;
236         if(m_MinNode) freeAll(m_MinNode);
237     }
238 
239     void insert(const reference key)
240     {
241         FibonacciHeapNode* x=newNode();
242         x->key=key;
243         if(m_MinNode==NULL)
244         {
245             x->left=x->right=x;
246             m_MinNode=x;
247         }
248         else
249         {
250             assert(x);
251             insertNode(x,m_MinNode);
252             if(x->key<m_MinNode->key) m_MinNode=x;
253         }
254         m_NodeNumber++;
255     }
256 
257     value_type getMinValue()
258     {
259         return m_MinNode->key;
260     }
261 
262     /**
263        将h合并到该树上
264        之后将销毁h
265     **/
266     void UnionHeap(FibonacciHeap* &h)
267     {
268         if(h->m_MinNode==NULL) return;
269 
270         if(m_MinNode==NULL)
271         {
272             m_MinNode=h->m_MinNode;
273             m_NodeNumber=h->m_NodeNumber;
274         }
275         else
276         {
277             FibonacciHeapNode* S=h->m_MinNode;
278             FibonacciHeapNode* E=S->right;
279 
280             FibonacciHeapNode* curS=m_MinNode;
281             FibonacciHeapNode* curE=curS->right;
282             E->left=curS;
283             curS->right=E;
284             curE->left=S;
285             S->right=curE;
286 
287             if(h->m_MinNode->key<m_MinNode->key)
288             {
289                 m_MinNode=h->m_MinNode;
290             }
291         }
292 
293         m_NodeNumber+=h->m_NodeNumber;
294         delete[] h;
295         h=NULL;
296     }
297 
298     void removeMinValue()
299     {
300         if(m_MinNode==NULL) return;
301         FibonacciHeapNode* z=m_MinNode;
302         if(z->son)
303         {
304             FibonacciHeapNode* sonBegin=z->son;
305             FibonacciHeapNode* curSon=sonBegin;
306             int chainNum=0;
307             do
308             {
309                 curSon->father=NULL;
310                 curSon=curSon->left;
311                 chainNum++;
312             }while(curSon!=sonBegin);
313             curSon=sonBegin;
314             for(int i=0;i<chainNum;i++)
315             {
316                 FibonacciHeapNode* next=curSon->left;
317                 insertNode(curSon,m_MinNode);
318                 curSon=next;
319             }
320         }
321 
322         if(z->left==z)
323         {
324             m_MinNode=NULL;
325         }
326         else
327         {
328             z->left->right=z->right;
329             z->right->left=z->left;
330             m_MinNode=z->left;
331             consolidate();
332         }
333         delete z;
334         m_NodeNumber--;
335     }
336 
337     void decreaseKey(FibonacciHeapNode* x,const reference key)
338     {
339         assert(x&&x->key>key);
340         x->key=key;
341         FibonacciHeapNode* y=x->father;
342         if(y!=NULL&&x->key<y->key)
343         {
344             cut(x,y);
345             cascadingCut(y);
346         }
347         if(x->key<m_MinNode->key) m_MinNode=x;
348     }
349 
350     /**
351       删除指针x
352     **/
353     void remove(FibonacciHeapNode* x)
354     {
355         if(x==NULL) return;
356         decreaseKey(x,m_MinValue);
357         removeMinValue();
358     }
359 
360     /**
361       删除x
362     **/
363     void remove(const reference x)
364     {
365         remove(search(x));
366     }
367 
368     /**
369       查找key 返回一个指针 找不到返回NULL
370     **/
371     iterator search(const reference key)
372     {
373         return search(m_MinNode,key);
374     }
375 
376 };