Priority Queue in C++

The Standard Template Library (STL) in C++ offers several containers to manage data efficiently, and one of the most powerful among them for ordered task handling is std::priority_queue. This container adaptor provides constant-time access to the largest element, making it ideal for problems where priority-based retrieval is essential. In this article, we will discuss what is a priority queue, its time complexity, syntax, functions, and real-life applications in C++.

Table of Contents:

• What is a Priority Queue in C++?
• Priority Queue Working
• Syntax of Priority Queue
• Functions in Priority Queue
• What is Heap Data Structure?
• Basic Operations
• Time Complexity
• Priority Queue vs Queue
• Priority Queue of Pairs or Tuples in C++ STL
• Real-Life Applications Using Priority Queue
• Conclusion

What is a Priority Queue in C++?

A priority queue in C++ is an abstract data structure based on a queue, but with an additional property that each element is associated with a priority. Elements get served by priority, and not by insertion order. Higher priority elements are to be dequeued over lower priority elements. A priority queue is ordered by the priority you give it (unlike a regular queue, which is FIFO), and for maintaining order, it uses the heap. By default, it is a max-heap, where the greatest element has the highest priority. As per the user’s requirement, we can change it to any desired priority. 

Priority Queue Working 

This priority queue in C++ uses a binary heap as its underlying container. Insertions and deletions maintain the heap property. Internally, it relies on make_heap, push_heap, and pop_heap algorithms. After every insertion/deletion, it keeps the largest/smallest at the top by rearranging elements. The top element is the one with the greatest (or least) priority, depending on your heap.

Syntax of Priority Queue 

priority_queue<T, c, comp> pq;

priority_queue<T, c, comp> pq; syntax is a generic declaration for a priority queue in C++. Here, T is the data type of priority queue (like int, string, or a custom class), C is the underlying element type to store the elements, which is vector<T> in general. That comp is the comparator that determines the ordering of the elements.

The Syntax for a Max-Heap Priority Queue:

std::priority_queue<int> maxHeap;

The above syntax declares the priority queue named maxHeap, which stores the int type elements. 

The Syntax for a Min-Heap Priority Queue

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

The above syntax declares the priority queue named minHeap, which stores the int type elements. 

C++ priority queue has a max-heap (or default max-heap) based on a vector container. The std::priority_queue maintains the heap property using std::make_heap, std::push_heap, and std::pop_heap. It prevents them from iterating or changing the elements directly. Each push/pop rearranges the heap, while top is O(1) and insertion/deletion is O(log n).

Functions in Priority Queue

• push() – Inserting the elements 
• pop() – Removes the top (highest/lowest priority) element.
• top() – Returns the top element.
• empty() – Checks if the queue is empty.
• size() – Returns the number of elements.

What is Heap Data Structure?

As mentioned in the introduction, the standard priority queue template of C++ is implemented using the binary heap. A binary heap is a complete binary tree, where all the nodes follow the heap property:

• Max-Heap: Parent ≥ children.
• Min-Heap: Parent ≤ children. This heap is stored as an array or vector so that we can access elements by index.

1. Min-Heap Priority Queue

Min-heap priority queue ensures the smallest element has the highest priority. It is useful in Dijkstra’s algorithm, Huffman encoding, etc. 

Example: 

Output: 

In C++, a min-heap can be created using std::priority_queue with std::greater<int> as the comparator. It keeps the smallest element at the top of the tree, which makes it easy to build a priority queue that allows for quick access and removal of the smallest element.

2. Max-Heap Priority Queue

std::priority_queue defaults to a max-heap. So the biggest element is always on top. It’s used in simulation, scheduling, and other contexts where we need the most important item first.  A max-heap is, by default, what std::priority_queue does, always putting the largest element on top.

Example: 

Output:

In the above code, we insert elements with push(), access the top with top(), and remove with pop(). This is convenient when you want fast access to the most important (largest) element, e.g., heapsort or greedy algorithms.

Applications

1. Scheduling tasks (CPU scheduling, bandwidth management)
2. Dijkstra’s algorithm for shortest paths
3. Huffman coding
4. A search algorithm
5. Real-time simulations where event timing matters

Basic Operations

In a priority queue, the basic operations are included with push() to insert, pop() to remove the elements, and empty() to check if the queue is empty. 

1. Inserting Elements

The push() function is used to insert elements into a priority_queue in C++. Calling push(value) maintains the heap property automatically. In case of a max or min heap, it is placed in order according to the comparator.

Example: 

Output: 

The above code adds 30, 10, and 50 to a max-heap. Internally, after each push, the heap is organised to put the largest number (50) on top. top() gives the highest, and pop() removes it while maintaining the heap property.

2. Accessing Elements

The top() function allows you to get the element with the highest priority in the priority queue. In a max-heap, top() gives max; In a min-heap, bottom. This operation finds the element for viewing, but does not remove it.

Example: 

Output: 

You can access the top via top(), which returns the highest (or lowest in min-heap) priority element in constant time.

3. Deleting Elements

Because priority_queue is based on a heap, pop() will always delete the top (highest-priority) element on the priority_queue. In a max-heap, that means the biggest element gets taken out; In a min-heap, the smallest. The pop() operation does not return the value, it only removes it from the queue.

Example: 

Output: 

In the code, pq. pop(): remove the top element of the priority queue, the maximum element (in case of max-heap). After calling pop(), the next element will sit at the top of the queue. The pop() function doesn’t return the removed element, it just removes it from the queue.

4. Pseudo Traversal

Priority_queue does not support direct traversal because that priority_queue cannot be traversed directly. After all, it is not a sequential container like a vector or a list. To iterate over it, you can keep calling top() and pop() to access and remove elements. This is known as pseudo-traversal, but it will delete the queue during the process unless you send a copy of it first.

Example: 

Output: 

We can access the elements in a priority queue by doing pseudo-traversal. Because priority_queue does not apply to direct traversal, this approach uses the queue unless you create a duplicate. It prints from largest to smallest for a max-heap or smallest to largest for a min-heap, depending on the comparator.

5. Changing Priority Queue Order

The std::priority_queue is a max-heap by default, but you can also use std::greater to create a min-heap by passing it as the comparator. In a min-heap, the element with the smallest value has the highest priority. This is achieved by providing three template parameters: type, container, and comparator.

Example: 

Output: 

We convert the priority queue into a min-heap by using std::greater. This is obtained by always keeping the smallest element on top and accessing it first. Now, instead of the default descending output, the output order is in ascending order.

6. Checking the Size of the Priority Queue

You check the number of elements in a priority_queue by using the size() function. It returns the current elements in the queue. This is helpful to check how many things are remaining or to limit loops during handling.

Example: 

Output: 

The above code uses the size() to return the number of elements currently in the queue. The size is 3 after adding three elements; It is 2 after removing one with pop(). This enables us to monitor queue utilisation and adjust application flow accordingly.

Time Complexity

• The time complexity for insertion is O(log n)
• The time complexity for removal (pop) is O(log n)
• The time complexity for accessing top (top) is O(1)

Priority Queue vs Queue

Priority Queue of Pairs or Tuples in C++ STL

However, in practice, we usually have to put complex data types such as coordinates, events, or weighted edges in our priority queue. To address this kind of case, C++ allows std::pair, std::tuple to be used as the data type of std::priority_queue. It is very useful in cases when you want to sort based on one field, but still want to keep the other values.

1. Using priority_queue

As an example, let’s say we keep the tasks as pairs {priority, task_id}. In the implementation of priority_queue, the component in the comparison function is the first value of the pair, and by default, this construct will create a max-heap. It compares the second if the first values are equal.

Example: 

Output: 

Here, tasks with the highest priority (largest number) are executed first. Output will begin with the pair {5, 103}, then yield {3, 104} and {3, 101} (note how it relies on the second value to break ties), and end with {1, 102}. This method is perfect for creating schedulers, job queues, or ranking systems.

2. Using priority_queue for Multiple Fields

We can also go for a priority_queue to store tuples and have multiple fields determining the priority (default is lexicographical, i.e., by the order of the tuple). This means you can create quite complex priority queues, for example, by multiple orders like first by one field, then by another.

Example: 

Output: 

This code stores and retrieves tasks ordered by priority. The tuple allows storing more detailed data while maintaining heap ordering. The default comparison checks the first field, then the second, and so on. You can use this format for event simulation, task managers, or even AI pathfinding, where multiple criteria matter.

Real-Life Applications Using Priority Queue 

Some of the real-life applications that use the priority queue: 

1. Task Scheduling System

In an operating system that lets you create different tasks, you would have different “Priorities” (High/Medium/Low) assigned to the tasks. This means that the task priorities have been accumulated, and the respective higher priority tasks are executed first, even though the lower priority task arrives first. This use case is well suited to a priority queue, since it allows us to efficiently retrieve the highest-priority task.

Example: 

Output: 

Tasks are added into a min-heap priority queue (<greater>) in such a way that lower priority values are processed first in this example. You are then sorting and processing the tasks based on their priority. Such a system can be extended to manage multiple concurrent tasks in a real-time fashion, applicable in servers or operating systems, or even distributed applications.

2. Event Simulation 

Let’s take an example, in simulations (especially in event-driven systems like customer service centres), you can use priority queues to simulate the arrival of events or requests, and their processing under certain required conditions. The events can be executed in a different order depending on the time they are received or the urgency of the request. Since events are processed in the order of their time, a priority queue is very useful in handling and processing these events.

Example: 

Output: 

In this case, an event is simply a priority level, a timestamp (i.e., when it arrived), and a description. The first is a priority_queue> that orders events by its first element, and therefore the smaller priorities come out first. This is an application that can also be extended for other services, such as a customer service centre, where urgent matters must be resolved before others, even if they were first in line.

Conclusion 

Priority Queue in C++ STL is an abstract data structure that serves elements based on priority instead of insertion order. It uses a max-heap by default, but can also change to a min-heap using custom comparators. It is capable of performing the operations: push(), pop(), top(), and size(). Priority queues are used in a wide variety of algorithms, including Dijkstra’s and real-time simulations. Priority queues offer efficient support for the retrieval of the element with the maximum (or minimum) priority, as well as logarithmic time complexity for insertion and removal of elements.

Priority Queue in C++ STL – FAQs