heap - 比 O(logn) 增加键更好的最小堆？

Question

我正在使用一个优先级队列，它最初将其元素的优先级基于启发式。随着元素出列，启发式方法会更新，并且当前队列中的元素可能会增加其键。

我知道有些堆（特别是斐波那契堆）已经摊销了 O(1) 减少键操作，但是是否有任何堆结构在增加键操作上有类似的界限？

对于我的应用程序，这远非性能问题（二进制堆工作正常），这实际上只是学术好奇心。

编辑：澄清一下，我正在寻找一种数据结构，其增加键操作的时间比 O(logn) 快，而不是减少键。我的应用程序从不减少密钥，因为启发式高估了优先级。

Answer 1

二进制堆太不灵活，无法击败对数复杂性。二项式堆只是允许更有效的连接操作。

其他具有良好减少键性能的堆是配对堆和2-3 堆

Answer 2

实际上，对于斐波那契堆，增加键操作与减少键操作相同。恕我直言，将操作命名为“减少键”只是一种传统，因为它用于某些算法。但是斐波那契堆实现允许两者。

Answer 3

二项式堆需要 o(log n) 时间来减少关键操作！这不是比斐波那契堆慢吗？