算法导论斐波那契堆笔记

斐波那契堆相比普通的二项堆，主要区别在于它的性能更高，在合并堆、插入和 Decrease 等操作时具有更好的摊还性能。

个人认为二项堆的性能已经足够好了，书中居然说二项堆在 UNION 操作时性能很差，而这个很差的性能是 O(n)，对大部分操作来说这已经是性能的极限了。斐波那契堆的 UNION 操作只需要 O(1) 的摊还时间，确实有立场鄙视二项堆。

不过书中也说了，斐波那契堆的实用性并不太好，编程复杂，性能的常数因子大，主要是理论研究。

二项堆和斐波那契堆的 search 操作都比较低效（书中没有给出数值，我觉得这个低效的性能应该是 O(lgn)，大佬的鄙视链是没有上限的）。

斐波那契堆结构

斐波那契堆是一系列具有最小堆序的有根树的集合。

入口：堆的入口是整个堆中最小的元素，它处于一个双向循环链表中，这个链表叫根链表。所以结点会有 left 和 right 属性指向它的兄弟结点。

孩子：结点只有一个孩子属性，指向孩子链表的入口，这个入口背后同样是一个双向循环链表。

结点的 degree 属性表示其孩子链表的结点数目。

结点的 mark 属性表示该结点自从上一次成为另一个结点的孩子后，是否失去过孩子。（不是太明白这个描述，mark 属性是在调整堆的结构时使用）

可合并堆操作

创建堆
创建空堆的摊还代价为 O(1)

插入结点
插入操作很简单，初始化一个新的结点，加入到斐波那契堆的根链表中，完毕。摊还代价为 O(1)

寻找最小结点
最小结点就是斐波那契堆的入口结点 H.min，摊还代价为 O(1)

合并
合并操作就是把两个堆的根链表链接成一个，比较两个堆的入口结点选出合并后的入口结点

抽取最小结点
分为两步，第一步把入口结点（也就是最小结点）抽出，将它的子结点都添加到根链表中（这时候已经破坏了堆的性质）。第二步执行一系列复杂的合并恢复堆的性质。
可由一系列复杂的操作证明，Extarct 操作的摊还代价为 O(lgn)

关键字减值和删除一个结点

关键字减值的意思是，把某个结点的关键字减小，然后调整堆的结构。这个调整的过程比较复杂，涉及到 mark 属性的使用，以及“切断”和“级联切断”。

简单的描述减值操作的过程：
1.将结点的关键字修改后判断是否比父结点小，如果小就从原位置切下来，放到根链表中。
2.对父结点递归的执行“级联切断”
3.比较被减值的结点（现在在根链表中）与原 min 结点，选出新的 min 结点。

级联切断是一个向上递归的过程，到根链表中止，某一级中的操作为：判断结点是否被标记，如果被标记则执行“切断”并继续递归，如果没被标记，则标记该结点并中止递归。

可以证明“减值”操作的摊还代价为 O(1)（我表示惊呆）

删除结点的操作是由减值和 Extract 组成的，摊还时间为 O(lgn)

最大度数的界

通过一堆引理证明了斐波那契堆中任意结点的度数的上界 D(n) 为 O(lgn)。

顺便解释了斐波那契堆名字的由来：斐波那契来自斐波那契数列，堆与数列的关联在于堆的合并操作中，结点的 size（结点为根的子树中所有结点的数目）按数列增长。（这个关联是我自己解释的，并不严谨）