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++
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:
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++:
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)
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()
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
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()
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()
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)
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
C++ program to insert the new element in the priority queue
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
C++ program to access elements from the priority queue
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
C++ program to delete the elements in the priority queue
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
Difference between Queue and Priority Queue
Process the elements with the highest priority
No priority Exists
No principle applied
Follows FIFO principle
If more than one element with the same priority exists, the order of queue is taken
No such process undergoes
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
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.