我一直在寻找一种最小堆实现变体，它不是提供摊销的 O(1( 来减少密钥，而是提供 O(1( 来增加它。(权衡使用成本o(log(n((进行减少键操作(，因为正如这里所观察到的，这两件事同时是不可能的(。
我实际上有一组固定大小的元素，我想对键执行增量，或者用更大的元素替换最小的元素。因此，满足此条件的另一种方法也很棒！
有谁知道具有恒定摊销时间增加键操作的堆变化？
谢谢！
我认为你优化得太早了。我建议您使用配对堆启动并运行应用程序，然后对其进行分析。关于数据以及堆结构将如何执行，您还不知道太多的事情。
二项式堆、斐波那契堆、配对堆和许多其他变体相当难以分析，因为它们的行为在很大程度上取决于操作的组合、操作顺序和数据的性质。例如，在配对堆中，如果节点没有子节点，则增加键为 O(1(。节点是否有子节点取决于节点在堆中的位置以及调用了reduce 键或删除优先的次数。
我怀疑你会找到一个具有 O(1( 删除和对数插入的堆结构。即使是 Brodal 队列，它有 O(1( 用于其他所有内容，也是 O(log n( 用于删除。然而，请注意，尽管 Brodal 队列在渐近最优，但用 Brodal 自己的话来说，它"相当复杂"并且"在实践中不实用"。
让您的程序运行。剖析它。然后决定是否需要性能更高的优先级队列结构。
实际上你指向的链接说你不能一起进行的三个操作是insert、find-min和increase-keyO(1)。decrease-key操作不会进入其中。 因此，其他操作之一必须增加。 我怀疑这是否可能。
但话虽如此，斐波那契堆确实提供了摊销的随机O(1)键增加。 也就是说，对于一半的元素，您不需要移动它。 对于四分之一，您必须移动一次。 对于 1/8，您必须移动它两次，依此类推。 最坏的情况O(log(n))只有在您增加底部元素时才需要支付。 因此，增加随机元素的平均成本是O(1)。
您甚至可以使堆比这更好。 当您增加元素的值时，您可以将其标记为增加，并使实际冒泡变得懒惰。 除非它到达底部，否则您根本不需要移动它。 因此，根据使用情况，大多数时候您无需为移动东西付费。