Chinaunix首页 | 论坛 | 博客
  • 博客访问: 490723
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2012-04-14 22:48:13

     在所有的堆数据结构中,效率最高的为Fibonacci堆,插入复杂度为O(1),删除复杂度为O(lgn),Fibnacci堆中将插入的元素调整转移到删除操作中,这样就将所有的堆调整转移到同一操作上,这也是它效率最高的原因之一,而且其中用到一个小技巧,设置了一个标志位,标志该节点从上次成为孩子节点后是否有丢失的孩子,用来提高调整的效率。

Fibonacci堆的数据结构:

点击(此处)折叠或打开

  1. struct fh_root {
  2.   struct fh_node *min;
  3.   struct list root;
  4.   unsigned long num;
  5. };

  6. struct fh_node {
  7.   unsigned long fh_parent_mark;
  8.   struct list sibling;
  9.   struct list child;
  10.   struct list list; //for parent list
  11.   unsigned long value;
  12.   unsigned long degree;
  13. } __attribute__((aligned(sizeof(long))));

支持的操作主要为:

提取Fibonacci堆的最小元素:

点击(此处)折叠或打开

  1. struct fh_node *fh_extract_min(struct fh_root * root);

Fibonacci堆插入一个元素:


  1. void fh_insert(struct fh_root *root,struct fh_node *node);

删除一个元素:


  1. int fh_erase(struct fh_root *root,struct fh_node *node);

代码较多,具体详见这里:


阅读(2488) | 评论(0) | 转发(1) |
0

上一篇:宏的妙用

下一篇:select 系统调用分析

给主人留下些什么吧!~~