在所有的堆数据结构中,效率最高的为Fibonacci堆,插入复杂度为O(1),删除复杂度为O(lgn),Fibnacci堆中将插入的元素调整转移到删除操作中,这样就将所有的堆调整转移到同一操作上,这也是它效率最高的原因之一,而且其中用到一个小技巧,设置了一个标志位,标志该节点从上次成为孩子节点后是否有丢失的孩子,用来提高调整的效率。
Fibonacci堆的数据结构:
- struct fh_root {
- struct fh_node *min;
- struct list root;
- unsigned long num;
- };
- struct fh_node {
- unsigned long fh_parent_mark;
- struct list sibling;
- struct list child;
- struct list list; //for parent list
- unsigned long value;
- unsigned long degree;
- } __attribute__((aligned(sizeof(long))));
支持的操作主要为:
提取Fibonacci堆的最小元素:
- struct fh_node *fh_extract_min(struct fh_root * root);
向Fibonacci堆插入一个元素:
- void fh_insert(struct fh_root *root,struct fh_node *node);
删除一个元素:
- int fh_erase(struct fh_root *root,struct fh_node *node);
代码较多,具体详见这里:
阅读(2488) | 评论(0) | 转发(1) |