Priority Queue - Insertion, Deletion and Implementation in C++

Programming is not all about writing code following any specific set of rules defined as a programming language. Programming is also used to store a large amount of data, process it, and access it whenever necessary to draw expected outputs. Therefore, every programming language supports a wide range of data structures which helps to store the huge data and access it accordingly. One such data structure is a queue.

The Queue is referred to as the collection of items in which the early added element is accessed first. The queue data type is further divided into various forms such as simple queue, circular queue, priority queue, double-ended queue, etc. In this article, let us study the priority queue in detail with all the necessary operations, examples, and applications.

What is Priority Queue?

A priority queue in C++ is a derived class in STL(standard template library) that processes only the highest priority element. It means that the first element of the queue is greatest from the rest of the elements of the queue. Later all the elements are arranged in non-increasing order, i.e., you can see each element of the queue has fixed priority.

The queue data structure follows the FIFO strategy, i.e., first in, first out, whereas the priority queue only checks the priority of the elements for retrieving the elements. Priority queues are implemented as container adapters. It is a class that uses an encapsulated object of a specific container class and deliver a specific set of member function to access the queue elements.

You can compare this strategy with the heap data structure where elements can be inserted at any moment, but only the maxheap elements can be retrieved. Similarly, the priority queue only retrieves the elements at the top and has the highest priority.

Below is the syntax of the priority queue in C++

priority_queue<int> variableName;  

Note that C++, by default, creates a max-heap while initiating the priority queue.  Therefore, when you wish to create the min-heap, the syntax is given by:

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

where vector is the standard template library, and the greater is the comparator class.

Methods of Priority Queue

Below are some of the methods offered by the priority queue in C++:

1) push()

Push() methods help to insert the element inside the priority queue. Initially, the element is added at the end of the queue and later, the elements arrange themselves according to the priority. The push() method takes the element to be inserted as the parameter.

For example: p.push(element)

2) pop()

The pop () method helps to delete the element from the priority queue according to the highest priority. As the element to be deleted is fixed according to the priority, the pop() method does not take any parameter.

For example: p.pop()

3) empty()

The empty () method helps to check whether the priority queue is empty or not. It returns the Boolean value as output, i.e., if the priority queue is empty, it will return true otherwise false. The empty () method does not take any parameter as shown below:

For example: p.empty

4) size()

Size() methods help to return the number of elements present in the priority queue. The return type of size() method is an integer displaying the size of the priority queue. Note that it does not take any parameters.

For example: p.size()

5) top()

The top() method returns the top element from the priority queue container. It does not take any parameter and pop the highest priority element placed at the top of the queue.

For example: p.top()

6) emplace()

Emplace() method helps to insert a new element at the top of the priority queue. It takes the element to be inserted as the parameter.

For example: p.emplace(element)

7) swap()

The swap () method helps to swap the elements of the priority queue with another priority queue. Remember that the size and type of both priority queues should be the same. Swap() method takes the priority queue as a parameter whose value needs to be swapped.

For example: p.swap(p1)

After understanding all the methods supported by the priority queue, the real question is: How does the c++ priority queue work? Let’s understand it in detail below.

How to implement Priority Queue in C++?

Priority Queue can be implemented using an array, binary search tree, linked-list, and heap data structure. However, the best choice is the heap data structure because it helps with relatively faster and efficient implementation of priority queues.

As mentioned earlier, C++, by default creates the max-heap while initiating a priority queue. Below are a few operations to implement priority queue(max-heap) in C++:

1) Insertion in Priority Queue

Inserting a new element in the priority queue is done by the following steps:

Inserting a new element at the end of the tree

Heapify the above tree

Heapifying the max-heap will arrange all the elements according to the priorities of the elements.

Algorithm for insertion operation in the priority queue

1) if no node is present, 
    create a newNode.
2) else (the node is present)
    insert the newNode at the end
3) perform heapify

C++ program to insert the new element in the priority queue

/* insertion operation in priority queue*/
 
#include
#include            //Header-file 
using namespace std;
 
int main()
{
priority_queue<int> p;
p.push(5);              // inserting elements 
p.push(4);
p.push(3);
while (!p.empty())
{
cout << ' ' << p.top();  //printing elements 
p.pop();
}
}

2) Accessing elements in Priority Queue

Priority Queue always retrieves the highest priority element i.e., the greatest element from the max heap without deleting the node.

Algorithm for accessing an element in the priority queue

1) return rootNode

C++ program to access elements from the priority queue

/* Program to access an element in priority queue*/
 
#include
#include     //Header-file 
using namespace std;
 
 
int main()
{
priority_queue<int> p;
p.push(5);    
p.push(4);
p.push(3);
p.push(2);
  
cout<<p.top();      //fetch element
priority(maximum element) 
}

3) Deletion in Priority Queue

For deleting a certain element from the priority queue(max-heap), you can follow below steps:

Selecting the element to be deleted

Now, you will swap it with the last element of the priority tree

Later, remove the last element as shown in the below image:

At last, due to swapping of the elements, you have to heapify the tree again to arrange the elements according to the priority.

Algorithm for deletion operation in the priority queue

1) if nodeToBeDeleted is the leafNode then
    delete the node
2) else swap lastLeafNode with the nodeToBeDeleted
    delete nodeToBeDeleted
3) perform heapify

C++ program to delete the elements in the priority queue

/* Program to delete elements in priority queue*/
 
#include
#include     //Header-file 
using namespace std;
 
int main()
{
priority_queue<int> p;
p.push(5);    
p.push(4);
p.push(3);
p.push(2);

  
p.pop();            
p.pop();         
 
while (!p.empty())
  {
        cout << ' ' << p.top();                
        p.pop();
    }
    
}

The max-heap is built by default while creating the priority queue. You must be wondering: what about min-heap? Well, in the case of min-heap, the insertion algorithm will be modified such that the root node is always smaller than its parent node. Similarly, the deletion operation will be updated such that the children node is smaller than the current node. However, for accessing the elements, the algorithm remains the same because the priority queue will always retrieve the highest priority element irrespective of its position.

C++ program to implement min-heap

#include
#include     //Header-file 
using namespace std;
int main()
{
     // creates a min heap
priority_queue <int, vector<int>, greater<int> > p;
 
    p.push(5);
    p.push(4);
    p.push(3);
    p.push(2);
    p.push(1);
    p.push(0);
      
     while (!p.empty())
    {
        cout <<"  "<< p.top() << " ";
        p.pop();
    }
  
    return 0;   
}

Difference between Queue and Priority Queue

Advantages of Priority Queue

• Easy to implement
• Processes with different priorities can be handled efficiently
• Application with differing requirements

Applications of Priority Queue

• Priority queue is used in Dijkstra's algorithm for finding the shortest path
• It is used in Prim’s algorithm to store keys of nodes at every step
• Priority queue is used in data compression
• Priority queue is used in Huffman Coding algorithm
• It is used in artificial intelligence algorithms such as the A* search algorithm
• It is used to implement a heap sort algorithm
• Priority queue is used in Operating System as the scheduling algorithm
• It is used in interrupt handling of your system
• Priority queue is used in CPU scheduling and Disk scheduling algorithm
• It is also used in Stack implementation

Conclusion

Identifying the priorities and doing tasks accordingly allows you with faster and effective results. Priority queue is one such data structure that helps you arrange your data according to your priority and make your tasks easy. Therefore, it is highly recommended to learn priority queue in C++ and take high advantage of all its applications.