优先级队列是否可以同时插入和删除O(1)？
可以使用堆实现优先级队列,并查看Fibonacci堆的运行时间,看起来每次删除不可能获得比O(logN)更好的运行时间.
我正在尝试实现一个数据结构,其中给定N个项目,我将在最大优先级队列中占一半,在最小优先级队列中占一半.然后我按顺序删除所有N个项目.
我可以在O(N)时间插入所有N个元素,但删除所有N个项目将采用O(N*logN),所以我想知道另一种方法是否更合适.
如果您可以构造具有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是常数 - 你的内存很快就会耗尽,扫描第一个非零元素可能需要一段时间.