FibonacciHeap是一种优先队列，它的性能如下图所示。 就平均而言有很好的性能，所以在一些图论算法中可以用来作改进算法的数据结构，尤其是那些稀疏图，总之是很好的工具。下面以设计者的角度简单描述我设计它的过程和思路。 1、组织方法采用C++提供的模板支持设计这个模板类，以达到很高的适应性。参数列表中只有一个类class T，它表示这个容器的元素类型，然后需要对它进行小的封装，封装的结果是得到一个内部小数据结构fibnode，如上图所示。 fibnode是组织FibonacciTree的结点结构，它包括了全部的指针和标记，整个FibonacciHeap就由它组成的，这个FibonacciTree在外部看来，只有一个min指针，指向它的根一层结点。 由于这样的组织形式，所以在析构的时候需要以递归的方式进行，递归的调用release()完成内存单元的回收。 这样的组织元素会遇到一个外部的问题，那就是内外数据的映射，由于元素是采用COPY的方式放入容器的，所以在内部是不知道哪个元素被封在哪个fibnode里，在内部确定一个元素的唯一方法就是找到它的fibnode指针，而为此如果做查找运算的话那它的优势将无法发挥出来。这个问题我没有在内部给出解决方法，原因是为了高适应性，因为这个T是未知的，所以我没办法给个O(1)的映射算法，如果用红黑树做Map，那会有O(lbn)的时间开销，那将使Decrease_Key()等调用的性能下降，唯一更好的办法是采用Hash表，而如果确定Hash函数又是和T有关的事情，所以这些事留给使用着在外部解决，根据具体的数据内容选择好的Hash函数，做外部的从T到const fibnode*的映射。值得说明的是，任何的fibnode指针都会在insert()过程的返回值中得到，如列程序所示： Heap::FibonacciHeap<int> h;const Heap::FibonacciHeap<int>::fibnode *x;x=h.insert(100); x将得到元素100的内部指针。于是可以将x作为Decrease_Key()的参数进行操作。 2、几个实现中的问题从FibonacciHeap的算法描述到实现其实不是太难，很多操作都轻而易举的事，我额外定义的内部过程有： remove(x)dblist_union(x,y) 分别表示从双端链表中删除一个元素，和合并两个双端链表，双端链表可以看成是环，对孩子的遍历或对兄弟的遍历都会变得非常容易实现，这是整个算法成功的关键。 刚才在写consolidate()过程时遇到逻辑错误，问题出在w跑整个root list的时候，在标记结果标志上是用的判断‘while(w!=min)’，而在这个过程中，min有可能被改变，去作为其它结点的孩子，所以出现错误。 还有一个问题就是在kill()过程（即算法描述中的delete()，为了和C++关键字区分开）需要定义一个负无穷大，而T的外部特性又不清楚，怎么办？我设了一个默认参数，标记是否是负无穷大，只要在进行比较的语句处多加一个判断即可，比较巧妙的避开了负无穷大的元素。 3、实现源码和说明本程序是自由代码可自由使用，其实是我的作业，没有兼容STL中的容器标准，STL中有PriorityQueue的标准容器，程序中也可能存在尚未发现的BUG，如果发现请告诉我。 由于是用的模板类，所以两个实现部分我也用了.h文件，如果用.cpp分有连接错误，当时我不知为什么，其实原因很简单，模板是采用所谓的晚连编，是在具体的class T定义的地方进行确定代码的，所以那些cpp不会被先编译，所以会出现连接错误。代码和BinaryHeap组织在一起，同在Heap的namespace下面。全部代码如下： //:priorityqueue.h文件，外部参数说明#include <vector>#ifndef HEAP_DEF_RICKONE_20061123#define HEAP_DEF_RICKONE_20061123namespace Heap{ //Binary Heap template <class T> class BinaryHeap {  std::vector<T> h;  int n; public:  BinaryHeap();  void max_heapify(int i);  void min_heapify(int i);  void insert(const T &e);  T minnum() const;  T extract_min();  void decrease_key(int x,const T &k);  void kill(int x); };  //Fibonacci Heap template <class T> class FibonacciHeap {  enum{NEGATIVE_INFINITY=1985};  struct fibnode  {   T data;   fibnode *p,*child,*left,*right;   int degree;   bool mark;  } *min;  unsigned long int n; public:  FibonacciHeap();//Construct a Heap  ~FibonacciHeap();  const fibnode* insert(const T &e);  T minnum() const;  T extract_min();  void decrease_key(const fibnode *x,const T &k,int TAG=0);  void kill(const fibnode *x);  void heap_union(FibonacciHeap<T> &h);  //for test  void Display();  void Print(int depth,fibnode *x); private:  void release(fibnode *x);  void remove(fibnode *x);  void dblist_union(fibnode *a,fibnode *b);  void consolidate();  void cut(fibnode *x,fibnode *y);  void cascading_cut(fibnode *y); };}#endif //:binaryheap.h BinaryHeap实现#include "priorityqueue.h" template <class T>Heap::BinaryHeap<T>::BinaryHeap(){ h.push_back(T()); n=1;} template <class T>void Heap::BinaryHeap<T>::max_heapify(int i){ //float up for(;i>1;) {  int p=i/2;  if(h[i]<h[p])  {   T temp(h[i]);   h[i]=h[p];   h[p]=temp;   i=p;  }  else   break; }} template <class T>void Heap::BinaryHeap<T>::min_heapify(int i){ //float down if(i<1 || i>=n)  return; for(;;) {  int left=i*2;  int right=left+1;  int smallest;  if(left>=n)   break;  if(right>=n)   smallest=left;  else  {   if(h[left]<h[right])    smallest=left;   else    smallest=right;  }  if(h[smallest]<h[i])  {   T temp(h[i]);   h[i]=h[smallest];   h[smallest]=temp;   i=smallest;  }  else   break; }} template <class T>void Heap::BinaryHeap<T>::insert(const T &e){ if(n>=h.size())  h.push_back(e); else  h[n]=e; n++; max_heapify(n-1);} template <class T>T Heap::BinaryHeap<T>::minnum() const{ if(n>1)  return h[1]; return T();} template <class T>void Heap::BinaryHeap<T>::decrease_key(int x,const T &k){ if(h[x]<k) {  //error warning  return; } h[x]=k; max_heapify(x);} template <class T>void Heap::BinaryHeap<T>::kill(int x){ if(x>=1 && x<n) {  h[x]=h[n-1];  min_heapify(x);  n--; }} template <class T>T Heap::BinaryHeap<T>::extract_min(){ if(n>1) {  T min=h[1];  kill(1);  return min; } return h[0];} //:fibonacciheap.h FibonacciHeap实现//中间包括一些原用于测试的代码，可去掉#include "priorityqueue.h" template <class T>Heap::FibonacciHeap<T>::FibonacciHeap(){ min=NULL; n=0;} template <class T>void Heap::FibonacciHeap<T>::release(fibnode *x){ if(x==NULL)  return; fibnode *p=x,*q; do {  q=p;  p=p->right;  release(q->child); } while(p!=x); do {  q=p;  p=p->right;  //printf("deleting %d ...\n",q->data);  delete q; } while(p!=x);} template <class T>Heap::FibonacciHeap<T>::~FibonacciHeap(){ release(min);} template <class T>void Heap::FibonacciHeap<T>::remove(fibnode *x){ if(x==NULL)  return; fibnode *l,*r; l=x->left; r=x->right; l->right=r; r->left=l; x->left=x; x->right=x;} template <class T>void Heap::FibonacciHeap<T>::dblist_union(fibnode *a,fibnode *b){ if(a==NULL || b==NULL)  return; fibnode *al=a->left,*bl=b->left; al->right=b; a->left=bl; bl->right=a; b->left=al;} template <class T>const Heap::FibonacciHeap<T>::fibnode* Heap::FibonacciHeap<T>::insert(const T &e){ fibnode *x=new fibnode; x->degree=0; x->p=NULL; x->child=NULL; x->left=x; x->right=x; x->mark=false; x->data=e; if(min==NULL)  min=x; else  dblist_union(min,x); if(e<min->data)  min=x; ++n; return (const fibnode*)x;} template <class T>T Heap::FibonacciHeap<T>::minnum() const{ if(min==NULL)  return T(); return min->data;} template <class T>void Heap::FibonacciHeap<T>::heap_union(FibonacciHeap<T> &h){ dblist_union(min,h.min); if(min==NULL || (h.min !=NULL && h.min->data < min->data))  min=h.min; n+=h.n; h.min=NULL;} template <class T>void Heap::FibonacciHeap<T>::consolidate(){ fibnode *A[32]={NULL}; fibnode *w=min; do {  fibnode *x=w;  w=w->right;  int d=x->degree;  while(A[d]!=NULL)  {   fibnode *y=A[d];   if(y->data < x->data)   {    fibnode *tmp=x;    x=y;    y=tmp;   }   //   if(y==min)   {    if(w==min)     w=min->right;    min=min->right;   }   remove(y);   if(x->child==NULL)    x->child=y;   else    dblist_union(x->child,y);   y->p=x;   x->degree++;   y->mark=false;   A[d]=NULL;   d++;  }  A[d]=x; } while(w!=min); for(int i=0;i<32;++i) {  if(A[i]!=NULL)  {   if(A[i]->data < min->data)    min=A[i];  } }} template <class T>T Heap::FibonacciHeap<T>::extract_min(){ if(min==NULL)  return T(); T z=min->data; fibnode *x=min->child; if(x!=NULL) {  while(x->right!=min->child)  {   x->p=NULL;   x=x->right;  }  x->p=NULL; } //add each child of z to the root list dblist_union(min,min->child); //remove z from the root list fibnode *r=min->right; remove(min); // if(r==min) {  delete min;  min=NULL; } else {  delete min;  min=r;  consolidate(); } --n; return z;} template <class T>void Heap::FibonacciHeap<T>::cut(fibnode *x,fibnode *y){ if(y->child==x) {  if(x->right==x)   y->child=NULL;  else   y->child=x->right; } remove(x); y->degree--; dblist_union(min,x); x->p=NULL; x->mark=false;} template <class T>void Heap::FibonacciHeap<T>::cascading_cut(fibnode *y){ fibnode *z=y->p; if(z!=NULL) {  if(y->mark==false)   y->mark=true;  else  {   cut(y,z);   cascading_cut(z);  } }} template <class T>void Heap::FibonacciHeap<T>::decrease_key(const fibnode *cx,const T &k,int TAG){ fibnode *x=(fibnode*)cx,*y=x->p; if(x->data < k)  return;//error "new key is greater than current key x" x->data=k; if(y!=NULL && (TAG==NEGATIVE_INFINITY || (x->data < y->data))) {  cut(x,y);  cascading_cut(y); } if(TAG==NEGATIVE_INFINITY || x->data < min->data)  min=x;} template <class T>void Heap::FibonacciHeap<T>::kill(const fibnode *cx){ decrease_key(cx,T(),NEGATIVE_INFINITY); extract_min();} //------------------------------FOR TEST----------------------------template <class T>void Heap::FibonacciHeap<T>::Display(){ Print(0,min);} template <class T>void Heap::FibonacciHeap<T>::Print(int depth,fibnode *x){ int i; if(x==NULL) {  for(i=0;i<depth;++i)   printf(" ");  printf("-\n");  return; } fibnode *p=x,*q; do {  q=p;  p=p->right;  for(i=0;i<depth;++i)   printf(" ");  printf("<%d> degree=%d\n",q->data,q->degree);  Print(depth+1,q->child); } while(p!=x);} //:test.cpp 测试与使用#include "binaryheap.h"#include "fibonacciheap.h" int main(void){ Heap::FibonacciHeap<int> h; const Heap::FibonacciHeap<int>::fibnode *x; int a[]={3,7,1,2,3,12,5,4,-23,-4,0,2,-54},t=1; int b[]={43,-23,12}; int i,n=sizeof(a)/sizeof(int); x=h.insert(a[0]); for(i=1;i<n;++i)  h.insert(a[i]); h.extract_min(); h.Display(); printf("-=-=-=-=-=-=-=-\n"); h.kill(x); h.Display(); printf("-=-=-=-=-=-=-=-\n"); printf("extract_min=%d\n",h.extract_min()); return 0;} rickone 2006/11/23

评论