斐波那契堆支持的操作有：

在不设计删除元素的操作仅需O(1)的平摊时间。

在实际情况中，斐波那契堆的常数因子以及程序上设计的复杂性，使得它没有二叉（或k叉）堆合适。因此，斐波那契堆主要具有理论上的意义。

斐波那契堆不能支持search操作，所以对于一些定点操作需要将结点指针作为输入的一部分。

斐波那契堆的结构

斐波那契堆由一组最小堆有序树组成，这里的有序仅仅是指根是树中最小的元素，其他不保证。

每个结点都有4个指针

如果没有左右兄弟的话，相应的左右兄弟指针都指向自身。没有父子结点的话相应指针则为nil。这也说明在相同高度的结点形成了一个双向链表，这样去掉一个结点以及合并两个表都可以在O(1)时间内完成。

每个结点还有其他两个域：

另外斐波那契堆还有两个值

势函数

采用势能方法来分析斐波那契堆的性能，对于一个给定的斐波那契堆H，t(H)表示堆中树的颗数，m(H)表示有标记的结点个数（结点的mark值为true），势定义为：

f(H) = t(H) + 2m(H)

最大度数

D(n) = O(lgn)

可合并堆的操作

对斐波那契堆上各种操作来说，关键思想是尽量把工作推后。

如果想要一次extract-min操作代价小，那么堆中的树的数目要尽量可能的少，为了保证这一点，要付出一定代价，例如可能要花lgn时间插入一个结点或者合并两个堆。

实际实现还是在extract-min时候做一些耗时工作。

创建一个斐波那契堆

只是生成一个空的堆对象H，代价为O(1)，势为0。

插入一个结点

增加的势只有一个多一颗树，为1。

合并两个堆

合并两个堆仅仅将跟表合并，然后将最小值的指针指向原来两个堆中的最小值中较小的那一个。

势没有发生改变。

抽取最小结点

将最小结点的孩子全部加入到根表当中，将最小结点从跟表中移除。
将最小结点指针置为原来最小结点右边结点指针，如果右边没有元素，那么置为nil。
依次遍历根表，将相同度数的树合并起来，这里是个递归操作，直到根表中相同度数的树合并完毕。
- 相同度数树合并引入了一个度数对应树根结点的数组A
- 循环根表时，如果A中有相同度数的树，那么把跟结点较大的树作为较小和树的最左孩子，形成的新树再尝试放入A中（这里可能有递归）
- 更新最小结点指针

在循环合并根表的过程中，总共有原先的 t(H) + 原先最小结点的孩子数D(n) - 原先最小结点1 颗树，每棵树最多只会成为其他树的子树一次。

所以循环的代价为t(H) + D(n) - 1。

势的变化最多为原先最小结点孩子全部都成为新树D(n) 。

总代价为 t(H) + D(n) - 1 + D(n) = O(D(n))。

减小一个关键字

删除一个结点

有了上面的两个操作，删除一个结点很简单。

最大度数的届

要证明上面的抽取最小结点的操作代价为lg(n)，那就要证明D(n)为O(lg(n))。