证明 - 优先级队列操作的时间复杂度

Question

我最近参加考试是有问题说：你的朋友想出了为执行以下操作的优先级队列中的一套算法：Insert(S, x)在O(1)，在O(1)Peek-Max(S)，Remove-Max(S)在O(1) ，以及Increase-Key(S, x, k)的O (logn)。你如何向你的朋友证明这套算法是不可能的？

我一直很紧张，因为我是积极的我得到了错误的答案。我说一个优先级队列必须具有这样的属性，对于一组元素[A1, A2, ... An]，它需要具有我现在认识的不正确的关系[A1 >= A2 >=...>= An]。只有第一个元素需要比其他元素更大（假设最大优先级队列）。因此，插入功能不能在O（1）中，因为对于一组n个元素，您无法确保放置的物品在固定时间内处于适当位置。

对于如何解决这个问题，你们有没有什么见解？昨晚我睡不着觉得我可能错了这个问题。

Answer 1

反驳一些事情的简单方法是想一个反例。在这种情况下，你想要找到一系列明显不可能的操作。

例如，假设您将n个元素插入到队列中，然后删除最多n个元素。由于这是优先级队列，因此我们提取的元素应该按排序顺序排列。因此，通过你朋友的算法，我们能够对n元素进行排序，时间复杂度为O(n)。我们知道排序最好是O(nlogn) - 排序O(n)是不可能的！