Priority Queue in C++

A?priority queue in c++ is a type of container adapter, which processes only the highest priority element, i.e. the first element will be the maximum of all elements in the queue, and elements are in decreasing order.

Difference between a queue and priority queue:

• Priority Queue container processes the element with the highest priority, whereas no priority exists in a queue.
• Queue follows First-in-First-out (FIFO) rule, but in the priority queue highest priority element will be deleted first.
• If more than one element exists with the same priority, then, in this case, the order of queue will be taken.

priority_queue<int> p1;

p1.push(35);????????????? // inserting element in a queue

p1.push(40);

p1.push(95);

while (!p1.empty())

{

cout << ' ' << p1.top();? //printing elements of queue

p1.pop();

}

the output will be : 95 40 35

Delete Elements from the priority queue

priority_queue<int> p1;

p1.push(35);???

p1.push(40);

p1.push(95);

p1.push(20);

// queue : 95 40 35 20

p1.pop();??????????? // queue :? 40 35 20

p1.pop();?????????? // queue :? 35? 20

?while (!p1.empty())

{

????????cout << ' ' << p1.top();???????????????

????????p1.pop();

????}

???Methods of Priority Queue:

Following are the methods of Priority Queue :

1. empty()?– This method checks whether the priority_queue container is empty or not. If it is empty, return true, else false. It does not take any parameter.

syntax?:?p1.empty()???????????// p1 is priority_queue object

1. size()?– This method gives the number of elements in the priority queue container. It returns the size in an integer. It does not take any parameter.

syntax :?p2.size()??????????????// p2 is priority_queue object

1. push()?– This method inserts the element into the queue. Firstly, the element is added to the end of the queue, and simultaneously elements reorder themselves with priority. It takes value in the parameter.

syntax :?p3.push(value)???????//value to be inserted

1. pop()?–?This method?delete the top element (highest priority) from the priority_queue. It does not take any parameter.

syntax :?p3.pop()?????// p3 is priority_queue object

1. top()?– This method gives the top element from the priority queue container. It does not take any parameter.

syntax :?p3.top()??

1. swap()?– This method swaps the elements of a priority_queue with another priority_queue of the same size and type. It takes the priority queue in a parameter whose values need to be swapped.

syntax :?p3.swap(p1)???

1. emplace()?– This method adds a new element in a container at the top of the priority queue. It takes value in a parameter.

syntax :?p3.emplace(value)??

The importance of the priority queue is to process the elements based on priority.

You can also implement the priory queue from scratch using the following data structures:?

• Arrays
• Linked list
• Heap data structure
• Binary search tree

Applications of Priority Queue:?

• CPU Scheduling
• Graph algorithms like?Dijkstra’s shortest path algorithm