Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficiency of the STL priority_queue

People also ask

What is the difference between set and priority_queue?

The priority queue only offers access to the largest element, while the set gives you a complete ordering of all elements. This weaker interface means that implementations may be more efficient (e.g. you can store the actual queue data in a vector , which may have better performance on account of its memory locality).

What does priority_queue pop return?

std::priority_queue::popRemoves the element on top of the priority_queue , effectively reducing its size by one. The element removed is the one with the highest value. The value of this element can be retrieved before being popped by calling member priority_queue::top .

What is std :: priority_queue?

std::priority_queue A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

How is STL priority queue implemented?

Priority Queue can be implemented using an array, binary search tree, linked-list, and heap data structure. However, the best choice is the heap data structure because it helps with relatively faster and efficient implementation of priority queues.


The priority queue adaptor uses the standard library heap algorithms to build and access the queue - it's the complexity of those algorithms you should be looking up in the documentation.

The top() operation is obviously O(1) but presumably you want to pop() the heap after calling it which (according to Josuttis) is O(2*log(N)) and push() is O(log(N)) - same source.

And from the C++ Standard, 25.6.3.1, push_heap :

Complexity: At most log(last - first) comparisons.

and pop_heap:

Complexity: At most 2 * log(last - first) comparisons.


top() - O(1) -- as it just returns the element @ front.

push() -

  • insert into vector - 0(1) amortized
  • push_into_heap - At most, log(n) comparisons. O(logn)

    so push() complexity is -- log(n)


No. This is not correct. top() is O(1) and push() is O(log n). Read note 2 in the documentation to see that this adapter does not allow iterating through the vector. Neil is correct about pop(), but still this allows working with the heap doing insertions and removals in O(log n) time.


If the underlying data structure is a heap, top() will be constant time, and push (EDIT: and pop) will be logarithmic (like you are saying). The vector is just used to store these things like this:

HEAP:
             1
        2         3
      8 12   11 9

VECTOR (used to store)

1 2 3 8 12 11 9

You can think of it as the element at position i's children is (2i) and (2i+1)

They use the vector because it stores the data sequentially (which is much more efficient and cache-friendly than discrete)

Regardless of how it is stored, a heap should always be implemented (especially by the gods who made the STD lib) so that pop is constant and push is logarithmic


C++ STL priority_queue underlying data structure is Heap data structure(Heap is a non linear ADT which based on complete binary tree and complete binary tree is implemented through vector(or Array) container.

ex  Input data : 5 9 3 10 12 4.

Heap (Considering Min heap) would be :

                   [3]
             [9]             [4]
         [10]    [12]     [5]


   NOW , we store this min heap in to vector,             
      [3][9][4][10][12][5].
      Using formula ,
      Parent : ceiling of n-1/2
      Left Child : 2n+1
      Right Child : 2n+2 .
  Hence ,
    Time Complexity for 
             Top = O(1) , get element from root node.
             POP()= O(logn) , During deletion of root node ,there  is      chance to violation of  heap order . hence restructure of heap order takes at most O(logn) time (an element might move down to height of tree).
            PUSH()= O(logn) , During insertion also , there might chance to violation of  heap order . hence restructure of heap order takes at most O(logn) time (an element might move up to root from leaf node).

Q1: I didn't look in the standard, but AFAIK, using vector (or deque btw), the complexity would be O(1) for top(), O(log n) for push() and pop(). I once compared std::priority_queue with my own heap with O(1) push() and top() and O(log n) pop() and it certainly wasn't as slow as O(n).

Q2: set is not usable as underlying container for priority_queue (not a Sequence), but it would be possible to use set to implement a priority queue with O(log n) push() and pop(). However, this wouldn't probably outperform the std::priority_queue over std::vector implementation.