Introduction To Priority Queue In C++ With Illustration.
Priority Queue is an extension of the queue that we discussed in our last tutorial.
It is similar to the queue in certain aspects and yet it differs from the ordinary queue in the following points:
- Each item in the priority queue is associated with a priority.
- The item with the highest priority is the first item to be removed from the queue.
- If more than one item has the same priority, then their order in the queue is considered.
=> Click Here For The Absolute C++ Training Series.
We can visualize the priority queue as a modified version of the queue except that when the item is to be taken off the queue, the item with the highest priority is retrieved first. So we prefer to use the priority queues instead of the queues when we need to process the items based on priority.
Table of Contents:
Basic Operations
Let us discuss some of the basic operations supported by the priority queue.
- Insert(item, priority): Inserts an item into the priority queue with a given priority.
- getHighestPriority(): Returns an item with the highest priority.
- deleteHighestPriority(): Removes an item with the highest priority.
Apart from the above operations, we can also use the normal queue operations like isEmpty (), isFull () and peek ().
Illustration
Let us see an illustration of the priority queue. For simplicity purposes, we will use ASCII characters as items in the priority queue. The higher the ASCII value, the higher is the priority.
Initial state – Priority Queue (PQ) – {} =>empty
From the above illustration, we see that the insert operation is similar to an ordinary queue. But when we call the “deleteHighestPriority” for the priority queue, the element with the highest priority is removed first.
Hence the first time when we call this function, item O is removed while the second time, the item M is removed as it has higher priority than G and A.
Implementation Of Priority Queues In C++
Priority queues can be implemented using:
#1) Arrays/ Linked lists
We can implement the priority queues using arrays and this is the simplest implementation for the priority queues.
To represent the items in the priority queue, we can just declare a struct as below:
struct pq_item{
int item;
int priority;
};
We have declared the priority as well for each item.
To insert a new item in the priority queue we simply have to insert the item at the end of the array.
To get the element from the queue using getHighestPriority (), we need to traverse the array from the start and return the item with the highest priority.
Similarly, to remove the item from the queue using the deleteHighestPriority operation, we need to traverse the entire array and delete the item with the highest priority. Then move all the other elements after the deleted item, one position back.
We can also implement the priority queue using a linked list. We can perform all the operations in a similar way like arrays. The only difference is that we need not move the elements after calling deleteHighestPriority.
#2) Heaps
Using heaps to implement a priority queue is the most efficient way and it provides a lot better performance when compared to the linked lists and arrays. Contrary to the linked list and array, heap implementation takes O (logn) time for insert and delete operations of the priority queue. Get operation, getHighestPriority takes O(1) time.
#3) In-built Priority Queue In Standard Template Library(STL) In C++
In C++, we have a priority queue as a container adaptive class, designed in such a way that the highest element is the first element in the queue and all the elements are in the decreasing order.
Thus each item in the priority queue has a fixed priority.
We have class <queue> in STL, which contains the priority queue implementation.
The various operations supported by the priority queue are as follows:
- priority_queue::size(): Returns the size of the queue.
- priority_queue::empty(): Checks if the queue is empty and returns its status.
- priority_queue:: top(): Returns a reference to the topmost element of the priority queue.
- priority_queue::push(): Adds an item at the end of the priority queue.
- priority_queue::pop(): Removes the first element from the priority queue.
- priority_queue:: swap (): Used to swap the contents of one priority queue with another one of the same type and size.
- priority queue value type: Value type gives the type of the element stored inside a priority queue. This also acts as a synonym for the template parameter.
- priority_queue:: emplace (): Used to insert a new element in the priority queue container at the top of the queue.
In the next program, we will see the functionality of the priority queue in STL in C++.
#include <iostream>
#include <queue>
using namespace std;
void displaypq(priority_queue <int> pq)
{
priority_queue <int> pqueue = pq;
while (!pqueue.empty())
{
cout << '\t' << pqueue.top();
pqueue.pop();
}
cout << '\n';
}
int main ()
{
priority_queue <int> pq;
pq.push(1);
pq.push(3);
pq.push(5);
pq.push(7);
pq.push(9);
cout << "Size of the queue(pq.size()): " << pq.size();
cout << "\nTop element of the queue(pq.top()): " << pq.top();
cout << "\nThe priority queue pq is : ";
displaypq(pq);
cout << "\nPriority queue, after pq.pop() operation : ";
pq.pop();
displaypq(pq);
return 0;
}
Output:
Size of the queue(pq.size()): 5
Top element of the queue(pq.top()): 9
The priority queue pq is: 9 7 5 3 1
Priority queue, after pq.pop() operation : 7 5 3 1
Java Implementation for Priority Queue
Priority queue in java is a special queue where all the elements in the queue are ordered according to natural ordering or custom ordering using a comparator supplied with the queue.
A priority queue in Java looks as shown below:
In Java priority queue, the elements are arranged such that the least element is at the front of the queue and the greatest element is at the rear of the queue. So when we remove the element from the priority queue, it is always the smallest element that is removed.
The class that implements the priority queue in Java is “PriorityQueue” and is a part of the collections framework of Java. It implements the “Queue” interface of Java.
Following is the class hierarchy for Java PriorityQueue class.
Given below is an Example of Priority Queue functionality with integers as items in Java.
import java.util.*;
class Main
{
public static void main(String args[])
{
// Create empty priority queue
PriorityQueue<Integer> priority_Queue =
new PriorityQueue<Integer>();
// Adding items to the priority_Queue using add()
priority_Queue.add(1);
priority_Queue.add(3);
priority_Queue.add(5);
priority_Queue.add(7);
// display the most priority element
System.out.println("peek()::Head value:" + priority_Queue.peek());
// Print all elements in Priotity queue
System.out.println("The priority queue:");
Iterator itr = priority_Queue.iterator();
while (itr.hasNext())
System.out.print(itr.next() + " ");
// poll() function to remove the queue elements
priority_Queue.poll();
System.out.println("\nAfter poll() function, priority queue:");
Iterator<Integer> itr2 = priority_Queue.iterator();
while (itr2.hasNext())
System.out.print(itr2.next() + " ");
// remove() function with priority queue
priority_Queue.remove(5);
System.out.println("\n\nAfter Remove(5) function, priority queue:");
Iterator<Integer> itr3 = priority_Queue.iterator();
while (itr3.hasNext())
System.out.print(itr3.next() + " ");
// Check if an element is present using contains()
boolean b = priority_Queue.contains(3);
System.out.println ( "\nPriority queue contains 3?: " + b);
// use toArray() function to get objects from the queue and display the array elements
Object[] arr = priority_Queue.toArray();
System.out.println ( "Array elements: ");
for (int i = 0; i<arr.length; i++)
System.out.println ( "Value: " + arr[i].toString()) ;
}
}
Output:
peek()::Head value:1
The priority queue:
1 3 5 7
After poll() function, priority queue:
3 7 5
After Remove(5) function, priority queue:
3 7
Priority queue contains 3?: true
Array elements:
Value: 3
Value: 7
In the above program, we make use of the PriorityQueue class of Java to create an object of PriorityQueue that contains an Integer object. We add elements into the queue using the “add” function. Then the poll() function is called and it deletes the element from the front of the queue which happens to be the least element.
Again we call the “remove()” function which removes the element specified as a parameter from the queue. We also use “Contains()” function to check if a particular element is present in the queue. Finally, we convert the queue into an array object using the “toArray()” function.
Application
- Operating system load balancing and interrupt handlers: Operating system functions like load balancing and interrupts handling is implemented using priority queues. The load balancing activity schedules the resources with the highest priority in order to effectively carry our load balancing. Interrupt handling is performed by servicing the interrupts with the highest priority. This functionality can be effectively implemented using the priority queues.
- Routing: Routing is a function that is used to route the network resources so that we get maximum throughput with minimum turnaround time. This can also be implemented using the priority queue.
- Hospital Emergency: In a hospital emergency room, the patients are attended according to how severe the condition of the patient is. This can be simulated using priority queues.
- Dijkstra’s Shortest Path Algorithm: Here the graph is stored as an adjacency list and we can use a priority queue to extract the minimum weighted edge efficiently from the adjacency list to implement Dijkstra’s shortest path algorithm.
- Priority queue can also be used to store node keys and extract the minimum key node while implementing spanning tree.
Conclusion
Priority queues are nothing but the extension of the queue. But unlike queues which add/remove items using the FIFO approach, in priority queue the items are removed from the queue according to the priority. Thus each item in the queue is associated with a priority and the item with the highest priority is the first one to be taken off the queue.
The priority queue has three main operations i.e. insert (), getHighestPriority () and deleteHighestPriority (). Priority queue can be implemented using arrays or linked list but the working is not very efficient. Priority queue can also be implemented using heaps and the performance is much faster.
In C++, we also have a container class <queue> that implements the functionality of a priority queue. In Java, there is a built-in class priority_queue that provides the functionality of a priority queue.
The priority queue is mainly used in applications that require items to be processed according to the priority. For Example, it is used in interrupt handling.
Our upcoming tutorial will explore all about circular queue which is yet another extension of the queue.
=> Visit Here For The Complete C++ Course From Experts.