优先级队列可能同时具有O（1）插入和删除吗？优先级队列O（1）插入和删除
优先级队列可以使用堆实现并查看斐波那契堆的运行时间，看起来每次删除的运行时间不可能比O（logN）好。
我想实现一个数据结构，其中给定N个项目，我将在最大优先级队列中占一半，在最小优先级队列中占一半。然后我会顺序移除所有N个项目。
我可以在O（N）时间插入所有N个元素，但删除所有N个项目将需要O（N * logN），所以我想知道另一种方法是否更合适。
如果你可以用O（1）插入和O（1）删除构造一个优先级队列，你可以用它在O（n）时间内对n个项目列表进行排序。正如在this answer中所解释的那样，在一般情况下无法对O（n）进行排序，因此无法在输入上进行更多假设的情况下构建O（1）插入和O（1）删除的优先队列。
例如，可以构造具有O（1）插入和O（k）（k是可插入的最大元素）移除的优先级队列。保留一个k链表。插入x只是在x列表的前面加上一个项目。删除必须扫描表以找到第一个非空列表（然后删除列表的第一个项目并返回该列表的索引）。只有k个列表，因此删除需要O（k）次。如果k是一个常数，那么可以解决O（1）的去除问题。
实际上，使用计数表会更好。除非您使用摊销分析（这是为什么我没有在前一段中使用它），否则递增可变长度整数不是恒定时间，但实际上无论如何您都不需要可变长度计数。另外，在实践中，对于大k来说，这会很糟糕，即使k是一个常数 - 你会很快耗尽内存，并且扫描第一个非零元素可能需要一段时间。
如果你可以有O（1）插入和O（1）删除，你可以使用它在O（n）时间排序列表。在一般情况下你不应该这样做。所以强烈反对这种可能性。 – harold 2013-03-26 20:09:42
@harold详细说明，有一个数学*证明*，比较种类的N个元素必须进行许多与'N log N'成比例的比较。所以除非你发现一个已经被同行评审致死的十年前结果的致命缺陷，就是这样。 **但**，对于特定类型的数据，如整数，您可以做得更好，因为您可以做比对比更多的事情（例如将它们分段或将它们用作随机访问集合的索引）。同样可以应用于优先级队列。但说实话，我从来没有听说过这样的数据结构。 – delnan 2013-03-26 20:25:21
@ harold-你真的应该把这个答案作为答案 - 我打算这样做，但是我不好意思盗走你的声望点。 :-) – templatetypedef 2013-03-27 03:49:11