Fibonacci 堆

     在所有的堆数据结构中，效率最高的为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);

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