A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values.

In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its priority value. For example, if you add an element with a high priority value to a priority queue, it may be inserted near the front of the queue, while an element with a low priority value may be inserted near the back.

Properties of Priority Queue

So, a priority Queue is an extension of the queue with the following properties.

• Every item has a priority associated with it.

• An element with high priority is dequeued before an element with low priority.

• If two elements have the same priority, they are served according to their order in the queue.

In the below priority queue, an element with a maximum ASCII value will have the highest priority. The elements with higher priority are served first.

How is Priority assigned to the elements in a Priority Queue?

In a priority queue, generally, the value of an element is considered for assigning the priority.

For example, the element with the highest value is assigned the highest priority and the element with the lowest value is assigned the lowest priority. The reverse case can also be used i.e., the element with the lowest value can be assigned the highest priority. Also, the priority can be assigned according to our needs.

Operations of a Priority Queue:

A typical priority queue supports the following operations:

1) Insertion in a Priority Queue

When a new element is inserted in a priority queue, it moves to the empty slot from top to bottom and left to right. However, if the element is not in the correct place then it will be compared with the parent node. If the element is not in the correct order, the elements are swapped. The swapping process continues until all the elements are placed in the correct position.

2) Deletion in a Priority Queue

As you know in a max heap, the maximum element is the root node. It will remove the element which has maximum priority first. Thus, you remove the root node from the queue. This removal creates an empty slot, which will be further filled with new insertions. Then, it compares the newly inserted element with all the elements inside the queue to maintain the heap invariant.

3) Peek in a Priority Queue

This operation helps to return the maximum element from Max Heap or the minimum element from Min Heap without deleting the node from the priority queue.

Types of Priority Queue:

1) Ascending Order Priority Queue

As the name suggests, in the ascending-order priority queue, the element with a lower priority value is given a higher priority in the priority list. For example, if we have the following elements in a priority queue arranged in ascending order like 4,6,8,9,10. Here, 4 is the smallest number, therefore, it will get the highest priority in a priority queue so when we dequeue from this type of priority queue, 4 will be removed from the queue and dequeue returns 4.

2) Descending order Priority Queue

The root node is the maximum element in a max heap, as you may know. It will also remove the element with the highest priority first. As a result, the root node is removed from the queue. This deletion leaves an empty space, which will be filled with fresh insertions in the future. The heap invariant is then maintained by comparing the newly inserted element to all other entries in the queue.

Types of Priority Queues

Difference between Priority Queue and Normal Queue?

There is no priority attached to elements in a queue, the rule of first-in-first-out(FIFO) is implemented whereas, in a priority queue, the elements have a priority. The elements with higher priority are served first.

Advantages of Priority Queue:

• It helps to access the elements in a faster way. This is because elements in a priority queue are ordered by priority, one can easily retrieve the highest priority element without having to search through the entire queue.

• The ordering of elements in a Priority Queue is done dynamically. Elements in a priority queue can have their priority values updated, which allows the queue to dynamically reorder itself as priorities change.

• Efficient algorithms can be implemented. Priority queues are used in many algorithms to improve their efficiency, such as Dijkstra’s algorithm for finding the shortest path in a graph and the A* search algorithm for pathfinding.

• Included in real-time systems. This is because priority queues allow you to quickly retrieve the highest priority element, they are often used in real-time systems where time is of the essence.

Disadvantages of Priority Queue:

• High complexity. Priority queues are more complex than simple data structures like arrays and linked lists, and may be more difficult to implement and maintain.

• High consumption of memory. Storing the priority value for each element in a priority queue can take up additional memory, which may be a concern in systems with limited resources.

• It is not always the most efficient data structure. In some cases, other data structures like heaps or binary search trees may be more efficient for certain operations, such as finding the minimum or maximum element in the queue.

• At times it is less predictable: This is because the order of elements in a priority queue is determined by their priority values, the order in which elements are retrieved may be less predictable than with other data structures like stacks or queues, which follow a first-in, first-out (FIFO) or last-in, first-out (LIFO) order.

#include <iostream>
#include <queue>

int main() {
    // Create a priority queue of integers (default is a max-heap)
    std::priority_queue<int> maxPriorityQueue;

    // Enqueue elements with different priorities
    maxPriorityQueue.push(30);  // Higher priority
    maxPriorityQueue.push(10);
    maxPriorityQueue.push(50);  // Highest priority
    maxPriorityQueue.push(20);

    // Dequeue elements (highest priority first)
    while (!maxPriorityQueue.empty()) {
        std::cout << maxPriorityQueue.top() << " ";  // Get the highest priority element
        maxPriorityQueue.pop();  // Remove the highest priority element
    }

    std::cout << std::endl;

    // Create a priority queue of integers as a min-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPriorityQueue;

    // Enqueue elements with different priorities
    minPriorityQueue.push(30);  // Lower priority
    minPriorityQueue.push(10);
    minPriorityQueue.push(50);  // Lowest priority
    minPriorityQueue.push(20);

    // Dequeue elements (lowest priority first)
    while (!minPriorityQueue.empty()) {
        std::cout << minPriorityQueue.top() << " ";  // Get the lowest priority element
        minPriorityQueue.pop();  // Remove the lowest priority element
    }

    std::cout << std::endl;

    return 0;
}