我一直在尝试实现堆数据结构以用于我的研究工作。作为其中的一部分，我正在尝试为最小堆实现增加键操作。我知道最小堆通常支持减少键。我能够为二进制最小堆编写增加 key 操作，其中，我递归地与最 child 子交换增加的 key 。
在斐波那契堆的情况下，在 this引用，他们说斐波那契堆也支持增加键操作。但是，我在 original paper 中找不到任何相关信息。在 Fibonacci 堆上，我在 CLRS(Cormen 的算法导论)中也找不到任何内容。
有人能告诉我如何才能有效地实现增加键操作，同时又不影响所有其他操作的数据结构的摊销边界吗？
最佳答案
首先，如果我们希望 insert 和 find-min 在斐波那契堆中保持 𝑂(1)，请注意 increase-key 必须是 𝑂(log𝑛)。
如果不是这样，您可以通过执行 𝑛 插入在 𝑂(𝑛) 时间内进行排序，然后反复使用 find-min 获得最小值，然后使用 ∀𝑥 将 𝜔 增加到头部:𝜔>𝑥 把头推到底。
现在，知道 increase-key 必须是 𝑂(log𝑛)，我们可以为它提供一个简单的渐近最优实现。要将节点 𝑛 增加到值 𝑥，首先要减少键 (𝑛,−∞)，然后删除最小值 ()，然后插入 (𝑛,𝑥)。
Refer here
关于algorithm - Min Fibonacci Heap - 如何实现增加键操作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57432502/