Runtime complexity of STL priority Queue

Priority Queue

In the C++ STL, a priority queue is a container adaptor. That means there is no primitive priorty queue data structure. Instead, you create a priority queue from another container, like a deque, and the priority queue's basic operations will be implemented using the underlying container's operations.
Priority queues are neither first-in-first-out nor last-in-first-out. You push objects onto the priority queue. The top element is always the "biggest" of the elements currently in the priority queue. Biggest is determined by the comparison predicate you give the priority queue constructor.

If that predicate is a "less than" type predicate, then biggest means largest.
If it is a "greater than" type predicate, then biggest means smallest.

Runtime complexity of STL priority Queue

Header

#include <queue> -- not a typo!

Constructors

priority_queue<T,   container<T>,   comparison<T> >   q;

Make an empty priority queue using the given container to hold values, and comparison to compare values. container defaults to vector<T> and comparison defaults to less<T>.

O(1)

Accessors

q.top();	Return the "biggest" element.	O(1)
q.size();	Return current number of elements.	O(1)
q.empty();	Return true if priority queue is empty.	O(1)

Modifiers

q.push(value);	Add value to priority queue.	O(log n)
q.pop();	Remove biggest value.	O(log n)