Priority Queue in C++

Contents

  1. Definition of Priority Queue
  2. Difference between Priority Queue and Queue
  3. Syntax of Priority Queue
  4. Syntax to create min-heap for Priority Queue
  5. How does Priority Queue work in c++?
    • Inserting elements
    • Accessing elements
    • Deleting elements
  6.  Methods of Priority Queue
  7.  Simple programs of Priority Queue
  8.  Conclusion

What is a Priority Queue?

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.

Syntax of Priority Queue :

  priority_queue<int> variableName;   

Note:  By default, C++ creates a max-heap for the priority queue.

Syntax to create min-heap for the Priority Queue:

  priority_queue <int, vector<int>, greater<int>> q; 

Where vector<int> is a STL container and greater<int> is comparator class.

How c++ Priority Queue works?

Priority Queue considers only the highest priority element.

Inserting elements in a Priority Queue – :

/* Program to insert elements in a queue*/

#include<iostream>
#include<queue>            //Header-file for queue
using namespace std;

int main()
{
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();
}
}
Screenshot (393)

Accessing elements in a Priority Queue :

/* Program to access an element of highest priority */

#include<iostream>
#include<queue>     //Header-file for queue
using namespace std;


int main()
{
priority_queue<int> p1;
p1.push(35);    
p1.push(40);
p1.push(95);
p1.push(25);
 
cout<<p1.top();      //fetch element of highest
priority(maximum element) i.e 95
}

Screenshot (397)

Deleting elements in a Priority Queue :

/* Program to delete elements in a queue*/

#include<iostream>
#include<queue>     //Header-file for queue
using namespace std;

int main()
{
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();
    }
   
}

Screenshot (399)

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)   

Lets see the above methods  with a  simple program :

A Program to show size and empty method:

#include<iostream>
#include<queue>         //Header-file for queue
using namespace std;
int main()
{
priority_queue<int> q1;
	
q1.push(25);          //add 25 in a queue
q1.push(15);    
q1.push(30);    
q1.push(76);    
q1.push(85);    
	             // queue : 85 76 30 25 15

cout<<" Number of elements in a priority queue : "<<q1.size()<<endl;
	
cout<<" The top element is : "<<q1.top()<<endl;       //return the maximum element from the queue;
	
q1.pop();        //remove the highest priority element(MAX element) from the queue;

	            // queue : 76 30 25 15

q1.push(55);
q1.push(89);
q1.push(35);
cout<<" After Inserting : "<<endl;
	            //queue : 89 76 55 35 30 25 15
	 
while(!q1.empty())
	 {
	 	cout<<" "<<q1.top()<<" ";
	 	q1.pop();
	 }
}
Screenshot (401)

Program of swap method : 

#include <iostream>  
#include <queue>  
using namespace std;  
int main()  
{   
priority_queue<int> p1,q1; 
 
//pushing value in p1.  
p1.push(28);  
p1.push(69);  
p1.push(36);  
p1.push(23);  
p1.push(14);  

//pushing value in q1.  
q1.push(10);  
q1.push(80);  
q1.push(32);  
q1.push(20);  
q1.push(15);  

p1.swap(q1);  
cout<< "elements in p1 : "; 
 
while(!p1.empty())  
{  

cout<<" "<<p1.top() <<' ';  
p1.pop();
  
} 
 
cout<< '\n';  
cout<< "elements in m1 : ";  
while(!q1.empty())  
{
  
cout<<" "<<q1.top() << ' ';  
q1.pop();  

    }  
return 0;
  
} 

Screenshot (405)

A Program of embrace method :

#include<iostream>
#include<queue>     //Header-file for queue
#include<string>
using namespace std;
int main()
{
	priority_queue<string> q1;
	q1.emplace("Ankit");
	q1.emplace("Ved");
	q1.emplace("Nikita");
	q1.emplace("Shaurya");
	q1.emplace("Anokhi");
	
	 // queue: Ved Shaurya Nikita Anokhi Ankit
t
	 
	while (!q1.empty())  
 {  

        cout<<" "<<q1.top() << " ";  
        q1.pop(); 
 
}   
return 0;
	
	
}
Screenshot (407)

C++ Program to implement min-heap : 

#include<iostream>
#include<queue>     //Header-file for queue

using namespace std;
int main()
{
	 // creates a min heap
priority_queue <int, vector<int>, greater<int> > p1;

    p1.push(55);
    p1.push(1);
    p1.push(76);
    p1.push(39);
    p1.push(23);
    p1.push(49);
    p1.push(32);
	 
	 while (!p1.empty())
    {
        cout <<"  "<< p1.top() << " ";
        p1.pop();
    }
 
    return 0;	
}
Screenshot (409)

Conclusion

Therefore, Priority Queue is a container which stores element with priority. Unlike queues, which insert or delete the element based on the FIFO rule, in Priority Queue, elements are removed based on priority. The element with the highest priority is the first one to be removed from the queue.

Priority queue supports three operations: is_empty to check if there is no element in the queue,insert_with_priority, to add an element with priority, and Pull_highest_priority_element, to fetch element of highest priority in the queue and show it.

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

This brings us to the end of the blog on the concept of Priority Queue in C++. We hope that you found this comprehensive and helpful and were able to gain the required knowledge. If you wish to up-skill and learn more such concepts, you can check out the pool of Free online courses on Great Learning Academy.

Also, if you are preparing for Interviews, check out these Interview Questions for C++ to ace it like a pro.


0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

1 × 1 =