What are Priority Queues in C++?

Introduction

A C++ data structure is called a priority queue. It resembles the queue in certain ways but varies from the typical queue in the following ways:

• Every entry in the priority queue has a priority assigned to it.
• The first thing to be taken out of the line is the one with the highest priority.
• The order of the queued items is taken into account if several items have the same priority.

The priority queue may be seen as a modified form of the queue with the exception that the item with the greatest priority is fetched first when an item is to be removed from the queue. Therefore, if we need to process things based on priority, we choose to utilize priority queues rather than queues.

Fundamental Operations

The priority queue supports certain basic activities.

• Insert(item, priority): Inserts an item with the specified priority into the priority queue.
• getHighestPriority(): Returns the highest priority item.
• deleteHighestPriority(): Removes the highest priority item.

In addition to the aforementioned actions, the standard queue operations such as isEmpty (), isFull (), and peek ().

Let's look at an example of the priority queue. We will utilize ASCII characters for the priority queue entries to keep things simple. The priority increases as the ASCII value rises. Priority Queue (PQ) initial state: empty

Implementation Of Priority Queues

1. Arrays/ Linked lists

Arrays may be used to implement priority queues, and this is the most straightforward way to do so. We just need to declare the following struct to describe the entries in the priority queue:

struct pq_item{

int item;

int priority;

};

For each item, we have also stated its priority. We only need to put the new item at the end of the array to add it to the priority queue.

We only need to put the new item at the ending of the array to add it to the priority queue. We must traverse the array starting at the beginning and return the item with the greatest priority in order to retrieve the item from the queue calling getHighestPriority ().

Similar to the last example, in order to delete the element from the queue by using deleteHighestPriority operation, we must iterate through the full array and remove the item with the highest priority. After that, shift all the components one place behind the removed item. A linked list may be used to construct the priority queue as well. In a manner similar to arrays, we are able to carry out all operations.

The only distinction is that after calling deleteHighestPriority, we don't need to relocate the pieces.

2. Heaps

The most effective technique to design a priority queue is using heaps, which performs far better than arrays & Linked Lists. The priority queue's delete & insert operations on the heap implementation take O (logn) time, in contrast to the linked list and array. O(1) time is required for the getHighestPriority action.

3. In-built Priority Queue In Standard Template Library(STL) In C++

A priority queue is a container adaptable class in C++ that is built so that the highest member appears first and all other elements are arranged in decreasing order. As a result, the priority queue's items all have set priorities. The STL has a class called "queue" that contains the implementation of the priority queue.

Functions associated with this data structure as highlighted below:

1. priority_queue::size(): size of the queue.
2. priority_queue::empty() -> Check for empty status
3. priority_queue:: top(): topmost element in PQ.
4. priority_queue::push(): Append item at end of PQ.
5. priority_queue::pop(): Delete first element of PQ.
6. priority_queue:: swap (): Switch content between two PQs of same size and length
7. priority queue value type: The element type kept in a priority queue is indicated by the value type. This serves as a replacement word for such template parameters.
8. priority_queue:: emplace (): used to add a new element to the container for the priority queue at the head of the queue.

STL Code

Applications

• OS load balancing & interrupt handlers: Priority queues are used to accomplish operating system features including load balancing and interruption management. To efficiently carry out our load balancing, the load balancing activity assigns the resources with the top priority. The highest priority interruptions are handled first when addressing interruptions. The priority queues are a useful tool for implementing this feature.
• Routing: Network resources are routed using the routing function to provide the highest throughput with the shortest turnaround times. The priority queue may be used to do this as well.
• Hospital Emergency: Patients in an emergency department at a hospital receive care in accordance with how serious their conditions are. Priority queues can be utilized to mimic this.
• Dijkstra’s Shortest Path Algorithm: Since the graph is being stored as an adjacency list, we can efficiently implement Dijkstra's shortest path algorithm by extracting the smallest weighted edge from the adjacency list using a priority queue.
• When building a spanning tree, a priority queue may also be utilized to store node keys and retrieve the minimum key node.

Conclusion

Priority queues are just an extension of the queue. However, unlike queues that add/remove entries using the FIFO method, priority queues delete things based on their priority. As a result, each item in the queue has a priority, and the item with the greatest priority is the first to be removed from the queue. There are three major operations in the priority queue: insert (), getHighestPriority (), and deleteHighestPriority (). (). Priority queues can be built with arrays or linked lists, however the operation is inefficient. Priority queues may also be built using heaps, and the performance is much improved. A priority queue's functionality is also implemented in C++ via the container class "queue".