Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 15 minutes

The **priority queue** in the STL of C++ is a dynamically resizing container to implement the special case of priority queye under the queue data structure. It is a sequential linear container. The top element of the priority queue is the greatest with all elements arranged in non-increasing order.

### Definition in `<queue>`

**std::priority_queue** is defined as follows under `<queue>`

header file:

```
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;
```

### Declaration

A **priority queue** with name **a** storing integers is declared as follows:

```
priority_queue<int> a;
```

### Functions

Assume the priority queue **a** to be:

and the priority queue **b** to be:

The following functions are defined under the `<queue>`

header file:

**a.empty()**: Returns**true**if the priority queue is empty,**false**otherwise.**a.size()**: Returns an integer indicating the**size**of the priority queue**a**.**a.swap(b)**: Swaps the contents of priority queue**a**with priority queue**b**.**a.emplace(x)**:**Places**the element**x**at the top of the priority queue**a**and then the queue is rearranged.**a.top()**: Returns a reference to the**top element**of the priority queue**a**.**a.push(x)**:**Inserts**the element**x**at the top of the priority queue**a**and then the queue is rearranged.**a.pop()**:**Removes**the element**x**at the top of the priority queue**a**.

For the above priority queue a, the function returns false.

For the above priority queue a, the function returns the integer 3.

For the above example, if the function is called, priority queue a becomes:

And priority queue b becomes:

For the queue a, if the function a.emplace(45) is called, a becomes:

For the above queue a, the function returns the integer 50.

For the queue a, if the function a.push(45) is called, a becomes:

For the queue a, if the function a.pop() is called, a becomes:

###### Note

- The worst case time complexity of inserting an element using emplace/push is `O(NlogN)` as the elements are reordered according to priority after insertion.
- Removing an element using pop operation is an `O(1)` operation as the element at the top is immediately removed.

### Illustration of Queue

```
// C++ code to illustrate priority queue in Standard Template Library (STL)
#include <iostream>
#include <queue>
using namespace std;
void display(priority_queue <int> a)
{
priority_queue <int> c = a;
while (!c.empty())
{
cout << '\t' << c.top();
c.pop();
}
cout << '\n';
}
int main ()
{
priority_queue <int> a;
a.push(10);
a.push(30);
a.push(20);
a.push(5);
a.push(1);
cout << "The priority queue a is : ";
display(a);
cout << "a.size() : \n" << a.size();
cout << "a.top() : \n" << a.top();
cout << "a.pop() : \n";
a.pop();
display(a);
return 0;
}
```

```
\\Console output
The priority queue a is : 30 20 10 5 1
a.size() : 5
a.top() : 30
a.pop() : 20 10 5 1
```