heap - 配对堆 - O(1) 用于减少键？

Question

我正在为我的一门课程做作业，一个问题要求显示减少键操作，对于配对堆，需要 O(1) 时间。

显然，如果您有一个指向要减少的键的指针，那么该操作将花费 O(1) 时间（只需删除链接，更改键值，然后合并）。

但是，在分配中没有任何地方说我们得到了一个指向键的指针。如果我们没有得到一个指针，那么 reduce-key 就不可能花费 O(1) 时间（你必须先在堆中查找键，这不会花费恒定时间）。我看了文献，都说减少键需要 O(logn) 时间。

我在这里错过了什么吗？

Answer 1

即使您有一个指向相关元素的指针，配对堆中减少键的摊销成本也不是 O(1)。已经证明，配对堆中减少键操作的摊销成本有一个 Ω(log log n) 下限。这不容易证明；有关详细信息，请参阅本文。