Fra*_*ffa 5 c++ algorithm priority-queue
我正在用C++编写一个应用程序,其中对优先级队列进行O(1)Dequeue操作至关重要,而Enqueue的复杂性并不是那么重要(当然,除非它变成n ^ 2或2 ^ n).
起初我使用了一个链表.这对Dequeue(O(1))来说非常好,并且它具有良好的入队复杂性.唯一的问题是,整理它.使用Insertion Sort,O(n)复杂度并不符合我的需求.但排序链表很麻烦.这是懒散的.
矢量并不好.Dequeue将是O(n)将所有元素移回一个地方.入队仍然是O(n)但速度要快得多.
你能建议更高效的方法吗？谢谢.
Fre*_*Foo 14
反向排序vector具有O(1)pop_back和O(n)插入.
NPE*_*NPE 10
您可以将队列存储为已排序的链接列表.移除前部元素是O(1)在正确的位置插入元素O(n).
但排序链表很麻烦.这是懒散的.
每次插入后,您不必执行完整排序.您所要做的就是遍历(已经排序的)列表以找到新元素的正确位置,并将其插入其中.遍历是O(n)和插入O(1).