Priority Queue in C++

Sometimes when we’re waiting in line at a store, certain people get to skip the line and move ahead. Similarly in a competitive setting, candidates with good marks are given priority. The candidate with the highest marks stands at the highest priority and is picked first for accolades. Operating on a very similar concept, a priority queue is a special type of queue in which each element is associated with a priority. Instead of being processed in a first-in, first-out (FIFO) order like a regular queue does, it is specifically designed such that the first element of the queue is either the greatest or the smallest of all elements in the queue and If two elements have the same priority, they are processed according to their order in the queue.

In the C++ Standard Template Library, the top element is always the greatest by default. However you can always change it to the smallest element at the top.

Here is a basic implementation in code using the STL priority_queue:

Syntax

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> pq;

    // Inserting elements
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // Displaying the highest priority element
    std::cout << "Top element: " << pq.top() << std::endl;

    // Removing the top element
    pq.pop();

    // Displaying the highest priority element after removal
    std::cout << "Top element after pop: " << pq.top() << std::endl;

    return 0;
}

Code Explanation 

• A priority queue (pq) is created, which stores integers in descending order (max at the top).
• Elements 10, 30, and 20 are inserted. The queue automatically arranges them as (30, 20, 10).
• pq.top() prints the largest element (30).
• pq.pop() removes the top element (30).
• pq.top() prints the new top element (20).

Code Output

Top element: 30
Top element after pop: 20

STL Priority Queue is the implementation of Heap Data Structure.

A heap is a special type of binary tree-based data structure that satisfies the heap property. The heap property is a data structure property that states that the value of a parent node is either greater than or equal to, or less than or equal to, the value of its child node. There are two types of heaps: min-heap and max-heap.

In a min-heap, the value of each parent node is less than or equal to the values of its children. This means that the smallest element is always at the root (top) of the heap.

In a max-heap, the value of each parent node is greater than or equal to the values of its children. This means that the largest element is always at the root (top) of the heap.

By default, priority queue implements a max-heap, which means that the largest element is always at the top.

Code

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(20);
    pq.push(15);

    // The largest element (20) will be at the top
    std::cout << "Top element (Max-Heap): " << pq.top() << std::endl; // Output: 20
    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl; // Output: 15

    return 0;
}

Output

Top element (Max-Heap): 20
Top element after pop: 15

Maximum Heap 

The largest element is always at the top (root). Insertion and deletion maintain this order.

Minimum Heap

The smallest element is always at the top.

How to Create Priority Queue in C++ with Heap Data Structure  

Here’s how we can implement priority queue using max heap in C++:

Code

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.push(10);
    maxHeap.push(50);
    maxHeap.push(30);

    std::cout << "Top element (Max Heap): " << maxHeap.top() << std::endl; // 50
    maxHeap.pop();
    std::cout << "Top element after pop: " << maxHeap.top() << std::endl; // 30

    return 0;
}

To create a min-heap, we use a custom comparator, such as the greater<int> comparator, which is used to reverse the default max-heap behavior, making it a min-heap (the smallest element is always at the top).

Code

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // Insert elements
    minHeap.push(50);
    minHeap.push(20);
    minHeap.push(30);

    // Display the smallest element
    std::cout << "Smallest element: " << minHeap.top() << std::endl;

    return 0;
}

Output

Smallest element: 20

The priority_queue by default while implementing max-heap uses the internal structure, vector (or any other container) and keeps the elements ordered in such a way that the root of the heap always has the largest element. This ensures the element with the highest priority is dequeued first. The push() method adds elements while maintaining the max-heap property. The pop() method removes the root (the largest element).

When we pass a comparator like greater<int>, the priority queue is internally implemented as a min-heap. This comparator ensures that the smallest element is at the top. The push() method inserts elements and maintains the min-heap property. The pop() method removes the root (the smallest element).

In both types of heaps, the heap property ensures efficient insertion and removal of the highest (or lowest) priority element, with a time complexity of O(logN) for both insertion and removal. 

The methods of a priority queue in C++ refer to the built-in functions provided by the Standard Template Library (STL) that allow you to interact with and manipulate the priority queue. 

Commonly used methods:

1. priority_queue::push(value): Inserts a new element into the priority queue and reorganizes the queue to maintain the priority order.
2. priority_queue::pop(): Removes the top element (highest-priority element) from the priority queue. The next highest-priority element becomes the new top element.
3. priority_queue::top(): Returns the element with the highest priority without removing it. It allows access to the top element for inspection.
4. priority_queue::empty(): Checks whether the priority queue is empty. Returns a boolean (true if the queue is empty, false otherwise).
5. priority_queue::size(): Returns the number of elements in the priority queue. It helps determine the size of the queue.
6. priority_queue::emplace(): Inserts a new element into the priority queue by creating it in place, avoiding unnecessary copies. It is faster than push() when the object being inserted requires creation, as it avoids creating a temporary object.
7. priority_queue::swap: Swaps the contents of the current priority queue with another queue. The queues must be of the same type even if the sizes are different.
8. Value_type: Represents the kind of object we have stored in a priority_queue.

The operations of a priority queue in C++ allow you to insert, remove, access, and manage elements based on their priority. These operations ensure efficient management of the data structure. 

1. Inserting Elements into a Priority Queue

This operation is used to insert a new element into the priority queue while maintaining the heap property (max-heap by default).

We can do this using either push() or emplace(). The push() method inserts a copy of the element, whereas the emplace() method constructs the element in place for efficiency.

Algorithm

1. Create a priority queue.
2. Insert an element using push() or emplace().
3. Maintain the heap property (max-heap by default).
4. The new element is placed in the correct position using heap operations.

Code

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    
    pq.push(50);  // Inserts element 50
    pq.emplace(20); // Constructs and inserts 20
    pq.push(30);  // Inserts element 30

    std::cout << "Top element after insertions: " << pq.top() << std::endl;

    return 0;
}

Output

Top element after insertions: 50

Explanation

• A max-heap priority queue is created.
• Elements 50, 20, and 30 are inserted.
• The highest priority element (largest number) is at the top.
• push() and emplace() maintain the heap property.

Time Complexity

Insertion: O(log⁡N) for each element.

2. Deleting Elements in a Priority Queue

This operation removes the highest-priority element (the top element) from the priority queue. After removal, the next element with the highest priority becomes the top.

The method used for this is pop().

Algorithm

1. Check if the priority queue is not empty.
2. Remove the highest-priority element using pop().
3. Maintain the heap structure by adjusting the elements.

Code

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(40);
    pq.push(10);
    pq.push(30);
    
    std::cout << "Top before pop: " << pq.top() << std::endl;
    
    pq.pop(); // Removes highest-priority element (40)
    
    std::cout << "Top after pop: " << pq.top() << std::endl;

    return 0;
}

Output

Top before pop: 40
Top after pop: 30

Explanation

• Elements 40, 10, and 30 are inserted.
• The element with the highest value (40) is removed using pop().
• The next highest element (30) becomes the new top.

Time Complexity

Deletion: O(log⁡N) per operation.

3. Accessing the Top Element

This operation returns the element with the highest priority without removing it. It allows us to see the element at the top of the queue. We use the method top() for this. 

Algorithm

1. Check if the priority queue is not empty.
2. Use top() to retrieve the highest-priority element without removing it.

Code

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(15);
    pq.push(50);
    pq.push(35);

    std::cout << "Top element: " << pq.top() << std::endl;

    return 0;
}

Output

Top element: 50

Explanation

• Elements are inserted into the priority queue.
• top() returns the highest-priority element (largest number).
• The element remains in the queue.

Time Complexity

Accessing Top: O(1)

4. Checking the Size of the Priority Queue

This operation returns the total number of elements present in the priority queue at the moment. It gives an idea about its size. We use the size() method for this. 

Algorithm

1. Use size() to get the number of elements in the priority queue.

Code

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(25);
    pq.push(60);
    
    std::cout << "Size of priority queue: " << pq.size() << std::endl;

    return 0;
}

Output

Size of priority queue: 2

Explanation

• Two elements are inserted.
• size() returns the total count of elements.

Time Complexity

Checking Size: O(1)

5. Checking if the Priority Queue is Empty

This operation is used to check whether the priority queue is empty or not. It returns true if it is empty and false if it is not empty. We use the empty() method here. 

Algorithm

1. Use empty() to check whether the queue is empty.
2. If it is empty, print a message; otherwise, display the top element.

Code

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    if (pq.empty()) {
        std::cout << "Priority queue is empty!" << std::endl;
    } else {
        std::cout << "Top element: " << pq.top() << std::endl;
    }

    pq.push(100);

    if (!pq.empty()) {
        std::cout << "Now, top element: " << pq.top() << std::endl;
    }

    return 0;
}

Output

Priority queue is empty!
Now, top element: 100

Explanation

• Initially, the priority queue is empty.
• The empty() function returns true, displaying a message.
• After inserting an element, empty() returns false, and top() displays the highest element.

Time Complexity

Checking Empty: O(1)

1. Forgetting that std::priority_queue is a max- heap by default and assuming the smallest element is on top.
2. Not checking whether the queue is empty or not before calling priority_queue::empty(). Doing this on an empty queue causes undefined behaviour.
3. Using priority_queue::pop() on an empty queue can also cause crashes.
4. Using std::greater<> or std::less<> incorrectly when defining a custom comparator.
5. Priority queues don’t iterate like normal data containers, so modifying them during a  traversal (iteration) is not possible.
6. std::priority_queue by default uses std::vector as the container. Changing the container improperly may cause compilation errors.

Tips to Reduce Errors 

•  Understand priority queue behavior (max-heap by default).
•  Use empty() before accessing top() or pop().
•  Define correct custom comparators when using objects.
•  Use a temporary queue for iteration.
•  Ensure the right underlying container is used.

Ordinary Queue Example

#include <iostream>
#include <queue>
int main() {
    std::queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    std::cout << "Front: " << q.front() << std::endl; // Output: 10
    q.pop();
    std::cout << "Front after pop: " << q.front() << std::endl; // Output: 20
    return 0;
}

Priority Queue Example

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(20);
    pq.push(30);
    std::cout << "Top: " << pq.top() << std::endl; // Output: 30 (highest priority)
    pq.pop();
    std::cout << "Top after pop: " << pq.top() << std::endl; // Output: 20
    return 0;
}

Priority queues are widely used due to their ability to efficiently manage elements based on priority.

1. Dijkstra’s Algorithm: Used in graph algorithms to find the shortest path from a source node to all other nodes. The algorithm uses a min-heap priority queue to select the node with the smallest distance at each step.
2. Huffman Coding: It's a compression algorithm that reduces the size of data by representing frequently occurring characters with shorter codes. The process involves building a Huffman Tree, and a min-heap priority queue is essential for constructing this tree. A min-heap priority queue is used to combine the two smallest frequency nodes repeatedly until a single tree is formed.
3. Task Scheduling: Priority queues are used in task management systems where tasks have different priorities. They help in scheduling tasks in order of priority, ensuring that more important tasks are completed before less important ones. 
4. Event Simulation: Used in simulations (e.g., traffic systems or event-based simulations) to manage events occurring at different times. Events are stored in a priority queue based on their timestamps. The event with the earliest timestamp is processed first.‍
5. Median Maintenance: Finding the median of a stream of numbers in real time. A combination of two heaps (min-heap and max-heap) is used to maintain elements on either side of the median.

Priority queues are powerful tools for managing data based on priority, making them more versatile than regular queues. In C++, the Standard Template Library (STL) provides an easy way to implement them, supporting both max-heaps (default) and min-heaps with simple configurations. Operations like adding, removing, and checking the top element are fast, with a time complexity of O(log⁡N).

These features make priority queues useful in many real-world applications, such as finding the shortest paths in graphs (Dijkstra’s algorithm), compressing data efficiently (Huffman coding), and managing tasks or events by priority. They are also used in simulations and to find the median of streaming data.

By understanding how priority queues work and how to use them, we can solve complex problems more efficiently. Their flexibility and speed make them an essential part of programming.

1. What are the real-life applications of priority queues?

Priority queues are used in diverse fields like hospitals, operating systems, flight reservations, etc.

2. What is the use of a Priority queue?

A priority queue stores elements with priorities, ensuring the highest (or lowest) priority element is processed first. It's used in scheduling, algorithms, and data compression.

3. Why priority queue is used in Dijkstra?

A priority queue in Dijkstra’s algorithm helps efficiently select the node with the smallest distance, speeding up the shortest path calculation.

4. Which queue is more efficient compared to others?

A priority queue implemented with a min-heap is generally more efficient, offering O(log n) time complexity for insertion and extraction of the minimum element. It is particularly efficient for algorithms like Dijkstra's.

5. What is the priority of the queue in C++?

In C++, a priority queue is a container adapter that stores elements in order of priority. By default, it’s implemented as a max-heap, where the largest element has the highest priority. It supports operations like `push()`, `pop()`, and `top()`.