Question

1.延迟合并操作

FIB-HEAP-INSERT 和 FIB-HEAP-UNION 只是最基础的链表合入操作，因为合并操作要尽可能地拖后

FIB-HEAP-EXTRACT-MIN 除了要完成本职工作外，还要作合并调整

2.合并调整操作

CONSOLIDATE 是作合并调整的函数

它将度数相同的根链接起来，直到对应每个度数至多只有一个根

遍历每一个根结点去判断，如果两个根结点的度是一样的，让大的结点作为小的结点的孩子

3.mark 的作用

为了防止堆太宽，需要策略来调整堆，使根结点成为别的根结点的孩子，该策略就是 CONSOLIDATE

同理，为了防止堆太深，也需要有相应的策略去调整，在适当的时候，把某个结点的孩子变成根

这一策略就是 CUT 和 CASCADING-CUT，mark 在实现这一策略的过程中起到辅助作用。

原理：当一个非根结点被切掉了 2 个孩子，就把它升为根结点

在删除一个结点时，怎么区分是第一个被删除的孩子，还是第二个？此时需要用 mark 来标记

4.P300 那句话

因为翻译不好，严重影响理解

一旦第二个孩子也失掉后，x 与其父结点之间的联系就被切断了，并成为一个新根。

原文：As soon as the second child has been lost, we cut x from its parent, making it a new root.