5

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.

Improve this question
5
  • In the question you say, "it's not so important the complexity of Enqueue (well unless it becomes n^2 or 2^n of course)". Then in comments you say that reallocating a vector (which is O(n)) is too slow. Make your mind up :-) Commented May 28, 2012 at 11:45
  • I don't get two things: (1) sorting a linked list with merge sort is very easy. (2) if you enqueue all objects into the list, there is no need to sort it as it will be already sorted. Linked list with simple insertion into the correct place has O(1) dequeue and O(n) enqueue already. No sorting is needed. Strange. Commented May 28, 2012 at 11:51
  • @SteveJessop to me it's more important the Dequeue operation. However I don't wan't the Enqueue to be a bottleneck. This is going to be a piece in a very large software. And the list might contain hundreds of elements... Commented May 28, 2012 at 15:15
  • @antti.huima I'm using Insertion Sort as it's more efficient for already sorted lists than other sorts. And sure, it is more efficient to put elements in the right place. I just didn't tought it :( Commented May 28, 2012 at 15:17
  • 1
    @Alfa: note that over the long term, each element is added once and removed at most once. So heaps give best overall performance, since both operations can be O(log n). Unless you go into more detail what the specific requirements are that make it so important for remove to be faster than that, you won't get the best advice. Presumably it's in order to make the remover more responsive, to I/O or the GUI or something. By comparison with a heap, you want to give up overall performance in order to speed up remove. But you're not saying how much slower overall it should be. Commented May 28, 2012 at 15:18

5 Answers 5

Reset to default
14

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

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

well, this is good and I can't believe I didn't tought this before. However this would require reallocating the vector when it's full. Still too slow sorry.
@AlfaOmega08: I have no timings to prove this, but I suspect the periodic reallocation of a vector might be faster than all the small allocations done by a list.
@larsmans: anyway, if reallocation is the only problem with vector then you can try deque instead.
10

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).

Improve this answer

3 Comments

Yes, I guess my Sort method wasn't so smart... Knowing that it's already sorted will make the difference. This is the winner for the moment :)
This is the correct answer but I can't get myself to upvote it because it is at the same time completely trivial.
I gave a solution with O(1) delete-min [pop] and O(log n) insert [push]. Consider accepting my answer.
1

If you're willing to implement from the literature, then I have a much better solution for you.

Worst-Case Complexity

Delete: O(1)

Delete-min: O(1)

Find-min: O(1)

Insert: O(log n)

Reference

IF MELD is allowed to take linear time it is possible to support DELETE-MIN in worst case constant time by using the finger search trees of Dietz and Raman [3]. By using their data structure MAKEQUEUE, FINDMIN, DELETEMIN, DELETE can be supported in worst case time O(1), INSERT in worst case time O(log n) and MELD in worst case time O(n).

Brodal, Gerth Stølting. ‘Fast Meldable Priority Queues’. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, 282–290. WADS ’95. London, UK, UK: Springer-Verlag, 1995.

[3]: Dietz, Paul F, and Rajeev Raman. ‘A Constant Update Time Finger Search Tree’. Information Processing Letters 52, no. 3 (1994): 147 – 154.

Though this uses the RAM model of computation:

Our data structure uses the random-access machine (RAM) model with unit-cost measure and logarithmic word size;

More recently, a solution within Pointer-Machine model of computation has been given[1]. This has O(1) get-min, extract-min, get-max, extract-max and O(log n) insert.

[1]: Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. ‘Optimal Finger Search Trees in the Pointer Machine’. J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381–418.

Improve this answer

Comments

0

Boost now includes Boost.Heap, a library of heap data structures that also support priority queue operations. This page has a table of amortized complexities of the core operations for each of the provided data structures. A Fibonacci heap features: O(1) push, O(log(N)) pop, O(1) increase, and (if you need it) O(log(N)) decrease.

Improve this answer

4 Comments

None of them has O(1) pop, which the question claims is "critical". Of course sometimes people make mistakes, and think they need O(1) when in fact O(log n) is fine. In practice log n < 64, so O(log n) is a slowish O(1).
@SteveJessop: Yes, that is true. I know that OP said O(1) pop, but maybe there is a reason why OP requested a priority queue.
"priority queue" describes the functionality the questioner wants, not a particular kind of data structure. The underlying data structure (heap or something else), and the resulting complexities are an important implementation detail, but they don't affect whether or not the result is a priority queue. If the questioner truly needs a priority queue with O(1) pop then the usual heaps are excluded, and of course the performance of push will suffer accordingly.
Priority queue != heap. The former is an ADT that offers certain operations, without a specification of how they should be implemented.
0

It is possible to combine balanced binary search tree with linked list. Each element of the tree has links to its sons and also links to next a previous element. Then you can have:

O(lg n) insert, delete, search; O(1) - extract min+max

Another possibility is to use skiplist, if you don't mind using randomized structures. Than you will also have:

O(lg n) insert, delete, search; O(1) - extract min+max

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.