FIFO manner is used to implement a queue. In a queue, insertions are done at one end (rear) and deletion takes place at another end (front). Basically, the element enters first is deleted first. We implement a priority queue using c++ inbuilt functions.

Table of Contents

## Characteristics of Priority Queue

- A priority queue is an extension of a simple queue.
- In the priority queue, the elements do not follow FIFO.
- In priority queue on the basis of priority elements are deleted.
- Every element in the priority queue has a priority assigned to it.
- On the basis of that priority, elements are removed from the priority queue.
- The element with the highest priority is always at the top of the queue.
- Element with the lowest priority is always at the lowest of the queue

## Syntax

`priority_queue <int> pq;`

## Example

### Input

5,1,9,7,3

### Output

9,7,5,3,1

## Functions of Priority Queue

A priority queue in C++ supports various functions. Some of the functions are described below:

- push(): Insert an element in the queue.
- pop(): Delete the lowest priority element from the queue.
- size(): the length of the priority queue is returned.
- empty(): if the priority queue is empty return true else returns false.
- top(): highest priority element is returned.
- swap(): Copies the element to another priority queue of similar size and type.
- emplace(): Inserts an element in the priority queue at the top.

## Implementation

Implementation of priority queue is possible using various data structures such as an array, linked list, or heap. The most efficient and simple way to implement a priority queue is by using a heap. Heaps are preferred over any other data structure because heaps provide better performance than other data structures.

In C++ we are provided a stl library for priority queue which can be used easily to implement a priority queue.

#include <iostream> #include <queue> #include<stdlib.h> using namespace std; int pq_display(priority_queue <int> pq); int main () { priority_queue <int> pq; int num, choice; cout <<" 1 - Insert an element into queue" <<endl; cout <<" 2 - Delete first element from queue" <<endl; cout <<" 3 - Display queue elements" <<endl; cout <<" 4 - Display highest priority queue element" <<endl; cout <<" 5 - Exit" <<endl; while (1) { cout <<endl<< "Enter your choice : "; cin >> choice; switch (choice) { case 1: cout << "Enter value to be inserted : "; cin >> num; pq.push(num); break; case 2: cout << "The first element " << pq.top() <<" has been removed from the queue" <<endl; pq.pop(); break; case 3: pq_display(pq); break; case 4: cout <<"The highest priority element in the queue is " << pq.top() <<endl; break; case 5: exit(0); default: cout << "Choice is incorrect, Enter a correct choice"; } } return 0; } int pq_display(priority_queue <int> pq) { while (!pq.empty()) { cout <<pq.top() <<'\t' ; pq.pop(); } cout << '\n'; return 0; }

1 - Insert an element into queue 2 - Delete first element from queue 3 - Display queue elements 4 - Display highest priority queue element 5 - Exit Enter your choice : 1 Enter value to be inserted : 9 Enter your choice : 1 Enter value to be inserted : 7 Enter your choice : 1 Enter value to be inserted : 5 Enter your choice : 1 Enter value to be inserted : 3 Enter your choice : 1 Enter value to be inserted : 1 Enter your choice : 3 9 7 5 3 1

## Complexity Analysis of Priority Queue using C++

### Time Complexity

**O(N * log(n)) **where **“N” **is the number of insertions and deletions performed and **“n” **is the size of the priority queue.

### Space Complexity

**O(n)** where **“n” **is the number of elements in the priority queue.