algorithm - Fredman和Tarjan论文中斐波那契堆的DecreaseKey的原始设计

Question

我现在正在根据Fredman 和 Tarjan的原始论文实现斐波那契堆。如果我理解正确，根据论文，要执行节点x的DecreseKey操作，我们只需将其从其父节点中删除即可。但是如果减少后的键仍然大于其父键，那将是低效的（我认为）。此外，我看到许多设计仅在节点的密钥变得小于其父节点时才切断节点，例如在 CLRS 中。

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

Answer 1

我不能代表 Fredman 和 Tarjan（尽管我曾经审核过 Tarjan 的一个课程），但大概他们专注于 DecreaseKey 的最坏情况摊销复杂性，该优化对此没有影响。