heap - 优先级队列 O(1) 插入、删除最小和减少键？

Question

我在算法书中看到了这个关于优先级队列的“绝望挑战”：

“ O(1) 插入、删除最小和减少键。为什么不可能？”

是因为唯一的方法是用某种堆来实现它，而堆总是需要登录时间来删除最小（即使摊销）？

Answer 1

我假设一个众所周知的事实，即对 n 个整数进行排序需要时间 n * log(n) 并且我假设 delete-min 实际上找到了最小值（并且可以，例如返回它）。

面对矛盾，假设我们有一个像你描述的那样的数据结构。然后，为了对 n 个整数进行排序，我们首先将它们全部插入数据结构中，因此需要时间 O(n)。然后我们重复 delete-min 直到结构为空。这给了我们时间 O(n) 的排序整数，给我们一个矛盾。因此，该数据结构不存在。