Geek asks and answers

Priority queue with O (1) Dequeue and O (independently) Enqueue

I am writing a C ++ application where it is critical to have an O (1) Dequeue operation for the priority queue, while it is not so important, the complexity of Enqueue (well, if it does not become an n ^ 2 or 2 ^ n course).

At first I used a linked list. It was very good for Dequeue (O (1)), and he had good queue complexity. The only problem was sorting it. Not the fact that using Sorting Sorting, with O (n) complexity, could satisfy my needs. But sorting a linked list is a pain. It was sloooow.

Vector is not good at all. Dequeue will be O (n) to move all elements back. Enqueue will still be O (n), but much faster.

Can you suggest a more efficient method? Thank.

+5
source share
5 answers

You can save the queue as a sorted linked list. Removing the front element O(1)and inserting the element in the correct position O(n).

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

You do not need to do a full sort after each insert. All you have to do is move the list (already sorted) to find the correct position for the new item and paste it there. Bypass O(n), and insert O(1).

+10
source

Reverse-sorted vectorhas O (1) pop_backand O (n) insert.

+14
source

, .

: O (1)

-: O (1)

Find-min: O (1)

: O (log n)

MELD , DELETE-MIN , [3]. MAKEQUEUE, FINDMIN, DELETEMIN, DELETE O (1), INSERT O (log n) MELD O (n).

, . " Meldable Priority Queues. 4- , 282-290. WADS 95. , , : Springer-Verlag, 1995.

[3]: , . . ' . 52, . 3 (1994): 147 - 154.

RAM :

() ;

- [1]. O (1) get-min, extract-min, get-max, extract-max O (log n) insert.

[1]: , , , , . " . J. Comput. . Sci. 67, . 2 ( 2003 ): 381-418.

+1

Boost Boost.Heap - , . . Fibonacci: O (1) push, O (log (N)) pop, O (1) , ( ) O (log (N)) .

0

You can combine a balanced binary search tree with a linked list. Each element of the tree has links to its sons, as well as links to the next previous element. Then you can:

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

Another possibility is to use a skiplist if you are not opposed to using randomized structures. Then you will also have:

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

0
source

More articles:


All Articles