# Priority Queue

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

### Key Facts

**Gyroscopic Couple**: The rate of change of angular momentum () = (In the limit).

- = Moment of Inertia.
- = Angular velocity
- = Angular velocity of precession.

## 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:

- http://www.sgi.com
- http://support.microsoft.com/?ln=en
- Nicolai M. Josuttis: "The C++ Standard Library"

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