Priority Queue with O(1) Dequeue and O(whatever) Enqueue

Question

I'm writing an application in C++, where it's critical to have O(1) Dequeue operation for a Priority Queue, while it's not so important the complexity of Enqueue (well unless it becomes n^2 or 2^n of course) .

At first I used a linked list. It was very good for Dequeue (O(1)), and it had good enqueue complexity. The only problem was, sorting it. Not the fact that using Insertion Sort, with O(n) complexity it would have suited my needs. But sorting a linked list is a pain. It was sloooow.

A vector isn't good at all. Dequeue would be O(n) to move all elements a place back. Enqueue would be still O(n) but much faster.

Can you suggest more performant method? Thanks.

Answer 1

A reverse-sorted vector has O(1) pop_back and O(n) insert.

Answer 2

You could store the queue as a sorted linked list. Removing the front element is O(1) and inserting an element at the correct position is O(n).

But sorting a linked list is a pain. It was sloooow.

You don't have to perform a full sort after each insertion. All you have to do is traverse the (already sorted) list to find the correct position for the new element, and insert it there. The traversal is O(n) and the insertion is O(1).