斐波那契堆(Fibonacci heap)是一种可合并堆，可用于实现合并优先队列。它比二项堆具有更好的平摊分析性能，它的合并操作的时间复杂度是O(1)。
与二项堆一样，它也是由一组堆最小有序树组成，并且是一种可合并堆。
与二项堆不同的是，斐波那契堆中的树不一定是二项树；而且二项堆中的树是有序排列的，但是斐波那契堆中的树都是有根而无序的。
斐波那契堆的基本操作
1. 基本定义
复制代码
template
class FibNode {
public:
T key; // 关键字(键值)
int degree; // 度数
FibNode *left; // 左兄弟
FibNode *right; // 右兄弟
FibNode *child; // 第一个孩子节点
FibNode *parent; // 父节点
bool marked; // 是否被删除第一个孩子
FibNode(T value):key(value), degree(0), marked(false),
left(NULL),right(NULL),child(NULL),parent(NULL) {
key = value;
degree = 0;
marked = false;
left = this;
right = this;
parent = NULL;
child = NULL;
}
};
复制代码
FibNode是斐波那契堆的节点类，它包含的信息较多。key是用于比较节点大小的，degree是记录节点的度，left和right分别是指向节点的左右兄弟，child是节点的第一个孩子，parent是节点的父节点，marked是记录该节点是否被删除第1个孩子(marked在删除节点时有用)。
复制代码
template
class FibHeap {
private:
int keyNum; // 堆中节点的总数
int maxDegree; // 最大度
FibNode *min; // 最小节点(某个最小堆的根节点)
FibNode **cons; // 最大度的内存区域
public:
FibHeap();
~FibHeap();
// 新建key对应的节点，并将其插入到斐波那契堆中
void insert(T key);
// 移除斐波那契堆中的最小节点
void removeMin();
// 将other合并到当前堆中
void combine(FibHeap *other);
// 获取斐波那契堆中最小键值，并保存到pkey中；成功返回true，否则返回false。
bool minimum(T *pkey);
// 将斐波那契堆中键值oldkey更新为newkey
void update(T oldkey, T newkey);
// 删除键值为key的节点
void remove(T key);
// 斐波那契堆中是否包含键值key
bool contains(T key);
// 打印斐波那契堆
void print();
// 销毁
void destroy();
private:
// 将node从双链表移除
void removeNode(FibNode *node);
// 将node堆结点加入root结点之前(循环链表中)
void addNode(FibNode *node, FibNode *root);
// 将双向链表b链接到双向链表a的后面
void catList(FibNode *a, FibNode *b);
// 将节点node插入到斐波那契堆中
void insert(FibNode *node);
// 将"堆的最小结点"从根链表中移除，
FibNode* extractMin();
// 将node链接到root根结点
void link(FibNode* node, FibNode* root);
// 创建consolidate所需空间
void makeCons();
// 合并斐波那契堆的根链表中左右相同度数的树
void consolidate();
// 修改度数
void renewDegree(FibNode *parent, int degree);
// 将node从父节点parent的子链接中剥离出来，并使node成为"堆的根链表"中的一员。
void cut(FibNode *node, FibNode *parent);
// 对节点node进行"级联剪切"
void cascadingCut(FibNode *node) ;
// 将斐波那契堆中节点node的值减少为key
void decrease(FibNode *node, T key);
// 将斐波那契堆中节点node的值增加为key
void increase(FibNode *node, T key);
// 更新斐波那契堆的节点node的键值为key
void update(FibNode *node, T key);
// 在最小堆root中查找键值为key的节点
FibNode* search(FibNode *root, T key);
// 在斐波那契堆中查找键值为key的节点
FibNode* search(T key);
// 删除结点node
void remove(FibNode *node);
// 销毁斐波那契堆
void destroyNode(FibNode *node);
// 打印"斐波那契堆"
void print(FibNode *node, FibNode *prev, int direction);
};
复制代码
FibHeap是斐波那契堆对应的类。min是保存当前堆的最小节点，keyNum用于记录堆中节点的总数，maxDegree用于记录堆中最大度，而cons在删除节点时来暂时保存堆数据的临时空间。下面是斐波那契堆的属性结构图和内存结构图的对比示例。
从中可以看出，斐