data-structures - 优先队列 O(1) 插入和移除

Question

优先级队列是否可以同时具有 O(1) 插入和删除？

可以使用堆来实现优先级队列，并查看斐波那契堆的运行时间，似乎每次删除都无法获得比 O(logN) 更好的运行时间。

我正在尝试实现一个数据结构，其中给定 N 个项目，我将有一半在最大优先级队列中，一半在最小优先级队列中。然后我将依次删除所有 N 项。

我可以在 O(N) 时间内插入所有 N 个元素，但删除所有 N 个元素将花费 O(N*logN) 所以我想知道另一种方法是否更合适。

Answer 1

如果您可以构造一个具有 O(1) 插入和 O(1) 删除的优先级队列，则可以使用它在 O(n) 时间内对包含 n 个项目的列表进行排序。正如这个答案中所解释的，在一般情况下你不能在 O(n) 中排序，所以如果不对输入做出更多假设，就不可能构造一个具有 O(1) 插入和 O(1) 删除的优先队列.

例如，可以构造具有 O(1) 插入和 O(k)（k 是可以插入的最大元素）移除的优先级队列。保留一个包含 k 个链表的表。插入x只是将一个项目添加到第一个x列表的前面。删除必须扫描表以找到第一个非空列表（然后删除列表的第一项并返回该列表的索引）。只有 k 个列表，因此删除需要 O(k) 时间。如果 k 是一个常数，则可以去除 O(1)。

在实践中，使用计数表会更好。除非您使用摊销分析（这就是我在上一段中没有使用它的原因），否则递增可变长度整数不是恒定时间，但实际上您无论如何都不需要可变长度计数。此外，在实践中，即使 k 是常数，它也会对较大的 k 不利 - 您会很快耗尽内存并且扫描第一个非零元素可能需要一段时间。