正文

FibonacciHeap的C++模板实现2006-11-23 17:01:00

【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/rickone/20674.html

分享到：

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_20061123
namespace 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

阅读(7476) | 评论(4)


版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！

评论

loading...
您需要登录后才能评论，请 登录 或者 注册