我现在按照原来的Paper实现斐波那契堆弗雷德曼和塔里安。如果我理解正确,根据论文,要执行节点 x 的 DecreseKey 操作,我们只需将其从其父节点中删除即可。但是,如果减小后的键仍然大于其父级,那将是低效的(我认为)。此外,我看到许多设计仅在节点的键变得小于其父节点时才剪切节点,例如在 CLRS 中。
所以我对它的原始设计有点困惑。他们为什么不采用更有效的方法来执行 DecreaseKey。或者它可能使摊销分析更容易?任何回应表示赞赏。提前致谢。
最佳答案
我不能代表 Fredman 和 Tarjan(尽管我曾旁听过 Tarjan 的一节课),但大概他们关注的是 DecreaseKey 的最坏情况下的摊销复杂性,优化对其没有影响。
关于algorithm - Fredman 和 Tarjan 论文中 Fibonacci 堆的 DecreaseKey 的原始设计,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55149654/