练习题

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最大度的界