Priority Queue

Definition

The priority_queue template class is defined in the standard header <queue>, and in the nonstandard backward-compatibility header <stack.h>.

#include <queue>
namespace std {
  template < class T,
            class Container = vector<T>,
            class Compare = less<Container::value_type> >
  class priority_queue;
}

Description

The priority_queue is a Container Adapter that represents a collection of elements where only the largest element, determined by some comparison functor, can be accessed.

Priority_queue adapts any container that supports front(), push_back(), pop_back(), and has a random access iterator. In particular, deque and vector can be used. To instantiate a priority_queue, a comparison function object must be supplied.

A simple example of instantiating a priority_queue:

// a priority queue of integers sorted using std::less <> (default)
priority_queue <int> pqI; 
 
// a priority queue of doubles
priority_queue <double> pqD; 
 
// a priority queue of integers sorted using std::greater <>
priority_queue <int, deque <int>, greater <int> > pqIntegers_Inverse;

Performance

Priority_queue allows you to maintain a sorted collection of items determined by an associated comparator function, such as less, greater, etc. The top item therefore becomes the candidate of choice, lowest or highest based on the function chosen.
Since adapters do not support iteration, a priority_queue has no associated iterator.

The semantics of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. This is actually the procedure used by several sorting algorithms, once the layer of abstraction provided by the priority queue is removed.

This sorting method is equivalent to the following sorting algorithms:

• Heapsort
• Smoothsort
• Selection sort
• Insertion sort
• Tree sort

Priority_queue Operations

Create, Copy and Destroy Operations

Operation	Effect
priority_queue< El > pq	Creates an empty priority_queue pq which can hold values of type El
priority_queue< El > pq1(pq2)	Creates pq as a copy of pq2, whose component type must be El
priority_queue< El > pq1 = pq2	Copy constructor (alternate usage syntax)

Note: Any priority_queue will have a container data member (by default, a deque) which will hold its elements. That data member will have its own destructor which will automatically be invoked when the priority_queue goes out of scope.

Modifying Operations

Operation	Effect
pq1 = pq2	Assigns pq2 to pq1, and return the common value. The priority_queue on the left of an assignment receives the values and size of the one on the right
pq.top()	Returns a reference to the component of pq with the highest priority
pq.size()	Returns a value of type size_type giving the number of values currently in pq
pq.empty()	Returns true if pq is empty (contains zero values); otherwise returns false
pq.push(val)	Adds val to pq, increasing the size of pq by one
pq.pop()	Removes the value of pq with the highest priority, decreasing the size of pq by one