algorithm - Fredman 和 Tarjan 论文中 Fibonacci 堆的 DecreaseKey 的原始设计

Question

我现在按照原来的Paper实现斐波那契堆弗雷德曼和塔里安。如果我理解正确，根据论文，要执行节点 x 的 DecreseKey 操作，我们只需将其从其父节点中删除即可。但是，如果减小后的键仍然大于其父级，那将是低效的(我认为)。此外，我看到许多设计仅在节点的键变得小于其父节点时才剪切节点，例如在 CLRS 中。

所以我对它的原始设计有点困惑。他们为什么不采用更有效的方法来执行 DecreaseKey。或者它可能使摊销分析更容易？任何回应表示赞赏。提前致谢。

Answer 1

我不能代表 Fredman 和 Tarjan(尽管我曾旁听过 Tarjan 的一节课)，但大概他们关注的是 DecreaseKey 的最坏情况下的摊销复杂性，优化对其没有影响。