我一直在尝试实现堆数据结构以用于我的研究工作。作为其中的一部分，我正在尝试为最小堆实现增加键操作。我知道最小堆通常支持减少键。我能够为二进制最小堆编写增加密钥操作，其中，我递归地与最小的孩子交换增加的密钥。
在斐波那契堆的情况下，在这个参考文献中，他们说斐波那契堆也支持增加键操作。但是，我在关于 Fibonacci Heaps 的原始论文中找不到任何关于它的内容，在 CLRS（Cormen 的算法简介）中也找不到任何内容。
有人能告诉我如何有效地实现增加键操作，同时又不干扰数据结构对所有其他操作的摊销界限吗？
首先，请注意，如果我们希望 insert 和 find-min 在斐波那契堆中保持 (1)，则 increase-key 必须为 (log)。
如果不是，您可以通过插入 () 时间进行排序，然后重复使用 find-min 获得最小值，然后使用 ∀:> 在头部增加键以将头部推到结尾。
现在，知道 increase-key 必须是 (log)，我们可以为它提供一个简单的渐近最优实现。要将节点增加到 value ，首先要减少 key(,−∞)，然后 delete-min()，然后是 insert(,)。
参考这里