priority_queue

Overview

The standard library provides priority_queue where the highest valued element is stored first.

Details

priority_queue stores elements in priority based on the user supplied comparer. It's implementation is similar to a maxheap.

Syntax

The syntax is as below. Template parameter T represents the datatype to store and Container represents the container used for storage which can be vector or deque and Comparer represents the function used for comparison of the elements.

template < class T, class Container = vector<T>, class Comparer = less<T> > 
class priority_queue;

Members

 It defines following types

Name	Description
value_type	The first template parameter (T)
container_type	The second template parameter (Container)
value_compare	The third template parameter (Compare)
reference	value_type&
const_reference	const value_type&
size_type	an unsigned integral type

Operation

priority_queue can be graphically represented as below.

Internally it's stored as a heap. The highest value is the root of the heap. When new elements are added the heap is modified such that the highest value stays as root as per the Comparer argument. Similarly, when the top element is removed, the element with the next highest value will be the root element. 

Complexity

The complexity of access operation is O(1). Insertion or removal is O(N). 

Functionality

Constructors

In following constructors use default allocator. Custom allocators can be used by passing them as an additional argument.

Name	Description
priority_queue(const Comparer& cmp = Compare(),                     const Container&& cnt=Container())	Default Constructor. Contents of cnt will be moved.
Example: //v:{} priority_queue<int> v; //v2:{1,2,3,4} priority_queue<int,vector<int>,greater<int>> v2(greater<int>(),move(vector<int>{1,2,3,4})); //v3:{4,2,3,1} priority_queue<int,vector<int>> v3(less<int>(),move(vector<int>{1,2,3,4})); //v4:{4,2,3,1} priority_queue<int,deque<int>> v4(less<int>(),move(deque<int>{1,2,3,4}));
priority_queue(const Comparer& cmp, const Container& cnt)	Constructs priority_queue based on cnt and using comparison method.
Example: //v:{1,2,3,4} priority_queue<int,vector<int>,greater<int>> v(greater<int>(),vector<int>{1,2,3,4}); //v2:{4,2,3,1} priority_queue<int,vector<int>> v2(less<int>(),vector<int>{1,2,3,4}); //v3:{4,3,2,1} priority_queue<int,deque<int>> v3(less<int>(),deque<int>{1,2,3,4});
priority_queue(InputIterator first, InputIterator last,     const Comparer& cmp, const Container& cnt)	Constructs a priority_queue and copies the elements in the range along with the contents of cnt.
Example: int a[]{5,6,7}; //v:{1,2,3,6,5,7,4} priority_queue<int,vector<int>,greater<int>> v(begin(a),end(a),greater<int>(),vector<int>{1,2,3,4}); //v2:{7,6,5,1,2,3,4} priority_queue<int,vector<int>> v2(begin(a),end(a),less<int>(),vector<int>{1,2,3,4}); //v3:{7,6,5,1,2,3,4} priority_queue<int,deque<int>> v3(begin(a),end(a),less<int>(),deque<int>{1,2,3,4});
priority_queue(InputIterator first, InputIterator last,     const Comparer& cmp, const Container&& cnt=Container()	Constructs a priority_queue and copies the elements in the range along with the contents of cnt.
Example: int a[]{5,6,7}; //v:{7,6,5} priority_queue<int> v(begin(a),end(a)); //v2:{5,6,7} priority_queue<int,vector<int>,greater<int>> v2(begin(a),end(a)); //v3:{7,6,5} priority_queue<int,deque<int>> v3(begin(a),end(a)); //v4:{1,2,3,6,5,7,4} priority_queue<int,vector<int>,greater<int>> v4(begin(a),end(a),greater<int>(),move(vector<int>{1,2,3,4})); //v5:{7,6,5,1,2,3,4} priority_queue<int,vector<int>> v5(begin(a),end(a),less<int>(),move(vector<int>{1,2,3,4})); //v6:{7,6,5,1,2,3,4} priority_queue<int,deque<int>> v6(begin(a),end(a),less<int>(),move(deque<int>{1,2,3,4}));
priority_queue(const priority_queue& x)	copy constructor
priority_queue (priority_queue&& x)	move constructor

Capacity

Name	Description
size_type size()	Returns the number of elements. Call size() method on the container. Example: int a[]{5,6,7}; //v:{7,6,5} priority_queue<int> v(begin(a),end(a)); //prints 3 cout << v.size();
bool empty()	Test whether container is empty. Calls isempty() method of the underlying container.

Element Access

Name	Description
reference top()	Returns reference to the top element.  It represents the root of the heap. Example: int a[]{5,6,7}; //v:{7,6,5} priority_queue<int> v(begin(a),end(a)); //prints 7 cout << v.top();

Modifiers

Name	Description
void push(const value_type& val)	Adds element. The underlying heap is modified. Example: //v:{} priority_queue<int> v; //v:{1} v.push(1); //v:{2,1} v.push(2);
void pop()	Removes the top element. The underlying heap is modified. Example: int a[]{5,6,7}; //v:{7,6,5} priority_queue<int> v(begin(a),end(a)); //v:{6,5} v.pop(); //v:{5} v.pop();
void swap(priority_queue & v)	Swaps the contents with v. Note T has to be same. Example: int a[]{1,2,3}; int a2[]{4,5,6}; //v:{1,2,3} priority_queue<int> v(begin(a),end(a)); //v2:{4,5,6} priority_queue<int> v2(begin(a2),end(a2)); //v2:{1,2,3} //v:{4,5,6} v2.swap(v);
void emplace(Args ...arg)	Constructs and inserts element using arg. The underlying heap is modified. Example: //v:{} priority_queue<int> v; //v:{1} v.emplace(1); //v:{2,1} v.emplace(2);