我正在用C++编写一个应用程序,对于优先队列来说,具有O(1)的Dequeue操作至关重要,而Enqueue的复杂度则不那么重要(当然,除非它变成了n^2或2^n)。
最初我使用了链表。它非常适合Dequeue(O(1)),而且具有很好的Enqueue复杂度。唯一的问题是排序它。并不是使用O(n)复杂度的插入排序适合我的需求,而是排列链表本身非常麻烦。这太慢了。
向量根本不好。Dequeue将是O(n),需要把所有元素向后移动一位。Enqueue仍然是O(n),但速度要快得多。
你能提供更高效的方法吗?谢谢。
O(n)
)太慢了。下定决心吧 :-) - Steve JessopO(log n)
。除非您详细说明了使删除操作比这更快速度如此重要的具体要求,否则您将无法获得最佳建议。可能是为了使删除器更加响应 I/O 或 GUI 等方面。与堆相比,您希望放弃整体性能以加快删除速度。但是您没有说整体上应该慢多少。 - Steve Jessop