Question

20.1 斐波那契堆

20.2 可合并堆

20.2-1

20.2-4

McGee 和 FibHeap 的区别在于合并的时机。

Fibheap 认为合并调整应该尽量地推迟，而 McGee 则在每次堆中结点有增加的时候就作合并调整。

个人认为，合并调整操作的意义是防止堆过宽而影响性能。但是从算法过程上看，根结点的个数多少不会影响 INSERT 和 UNION 的性能，因此没有必要。

比较认可 FibHeap 的做法。

20.3 减小一个关键字与删除一个结点

20.3-1

根据 P300 的描述，只有非根结点才可能被打上标记，如果根结点有标记，一定是它是非根结点的时候打上标记，然后被移到根结点的位置。

把结点移至根结点是通过上面代码中的函数 addNodeToRootList 和 addListToRootList 完成的，目标缩小至这两个函数周围

让根结点成为有标记结点，须满足以下两个条件

（1）调用这两个函数前，该结点是非根结点

（2）调用后没有清标记

结论：x 是 pMinData 的孩子，根据 P300 的步骤被打上标记后，执行 extract() 时又成为根结点

20.4 最大度的界