I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
ComputingStlContainersAdaptors

Priority Queue

A priority_queue is an Adaptor that provides a restricted subset of Container functionality: insertion, inspection and removal.

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

References:

Example:

Example - priority_queue of type double
Problem
This program works with a priority_queue of type double.
Workings
#include <iostream>
using std::cout;
using std::endl;
 
#include <queue>
 
int main()
{
   std::priority_queue< double > priorities;

priorities.push( 4.1 ); priorities.push( 10.7 ); priorities.push( 6.3 ); cout << "Values are: ";   while ( !priorities.empty() ) { cout << priorities.top() << ' '; priorities.pop(); }   cout << endl; return 0; }
Solution
Output:

Values are: 10.7 6.3 4.1