我一直在尝试实现堆数据结构以用于我的研究工作。作为其中的一部分，我正在尝试为最小堆实现增加键操作。我知道最小堆通常支持减少键。我能够为二进制最小堆编写增加键操作，其中，我递归地将增加键与最少的子级交换。
在斐波那契堆的情况下，在这个参考中，他们说斐波那契堆也支持增加键运算。但是，我在斐波那契堆的原始论文中找不到任何关于它的内容，在CLRS(Cormen算法简介(中也找不到任何内容。
有人可以告诉我如何有效地实现增加键操作，并且不会干扰所有其他操作的数据结构的摊销范围吗？
首先，请注意，如果我们希望插入和查找min保持O(1(，因为它们在斐波那契堆中，则增加键必须是O(logn(。
如果不是这样，您可以通过执行 n 次插入来在 O(n( 时间内进行排序，然后反复使用 find-min 来获得最小值，然后在头部增加键 ω 与 ∀x：ω>x 将头部推到最后。
现在，知道增加键必须是 O(logn(，我们可以为它提供一个简单的渐近最优实现。要将节点 n 增加到值 x，首先要减少键(n，−∞(，然后是 delete-min((，然后是 insert(n，x(。
参考这里