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.

4

5 回答 5

14

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

于 2012-05-28T11:16:26.560 回答
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).

于 2012-05-28T11:13:44.620 回答
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.

于 2013-01-05T09:17:33.310 回答
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.

于 2012-05-28T11:35:29.673 回答
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

于 2012-05-28T12:05:34.690 回答