Is the priority queue structure used?

Question

When searching for some functions in the documentation for the C ++ standard library, I read that push and pop for priority queues require constant time.

http://www.cplusplus.com/reference/stl/priority_queue/push/

Constant (in priority_queue). Although note that push_heap works in logarithmic time.

My question is, what data structure is used to support the priority queue using O (1) for push and pop?

Answer 1

I assume that you are linking to cplusplus.com .

Previously written on the page:

This member function effectively calls the push_back member function of the main container object, and then calls the push_heap algorithm to preserve the heap property priority_queues.

Thus, after pressing O(1) the data structure has lost its heap property, and then always follows it with O(log N) call to restore this property. In other words, operation O(1) is only one part of the whole operation; the complete operation is O(1) + O(log N) , which coincides with O(log N) .

I assume that they mention that the priority is the adapter, and they are trying to emphasize the difference between what the base container does versus what the adapter does.

Answer 2

The primary store for priority_queue can be a vector or deque or something similar that supports random access iterators. The storage is supported as a heap, not O (N) for push, so I suspect you read it incorrectly

Answer 3

Push and Pop start in logarithmic time according to

http://www.cppreference.com/wiki/stl/priority_queue/pop

http://www.cppreference.com/wiki/stl/priority_queue/push

Answer 4

I am skeptical about the statement O (1) ... where did you see it?

In any case, some notes on the implementation of the gcc priority queue .

Answer 5

There is no such heap. They wrote that it calls push_heap, which is logarithmic, so it is logn.

Answer 6

The standard defines these members in terms of push_heap and pop_heap , which implies compilation.

If this link says true (it says top also constant), why doesn't anyone implement universal O (N) using std::priority_queue ?

Secondly, this is what the link can say about in a very misleading way: the difficulty is push_back O (1) + push_heap (O (log N))