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

Question

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

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

对于我的应用程序，这绝不是性能问题(二进制堆可以正常工作)，它实际上只是出于学术上的好奇心。

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

Answer 1

二进制堆太不灵活，无法克服对数复杂性。
二项式堆仅允许更有效的联接操作。

其他具有良好降低键性能的堆是pairing heaps和2-3 heaps