Reading Time: 5 minutes
Published: 21 Feb 2025
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. 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:
#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;
}
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.
#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
Here's how we can implement priority queue using max heap in C++:
#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 comparator, which is used to reverse the default max-heap behavior, making it a min-heap (the smallest element is always at the top).
#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, 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(log N) 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.
priority_queue::push(value): Inserts a new element into the priority queue and reorganizes the queue to maintain the priority order.
priority_queue::pop(): Removes the top element (highest-priority element) from the priority queue. The next highest-priority element becomes the new top element.
priority_queue::top(): Returns the element with the highest priority without removing it. It allows access to the top element for inspection.
priority_queue::empty(): Checks whether the priority queue is empty. Returns a boolean (true if the queue is empty, false otherwise).
priority_queue::size(): Returns the number of elements in the priority queue. It helps determine the size of the queue.
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.
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.
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.
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.
#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;
}
Top element after insertions: 50
Insertion: O(log N) for each element.
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().
#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;
}
Top before pop: 40
Top after pop: 30
Deletion: O(log N) per operation.
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.
#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;
}
Top element: 50
Accessing Top: O(1)
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.
#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;
}
Size of priority queue: 2
Checking Size: O(1)
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.
#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;
}
Priority queue is empty!
Now, top element: 100
Checking Empty: O(1)
Forgetting that std::priority_queue is a max-heap by default and assuming the smallest element is on top.
Not checking whether the queue is empty or not before calling priority_queue::empty(). Doing this on an empty queue causes undefined behaviour.
Using priority_queue::pop() on an empty queue can also cause crashes.
Using std::greater<> or std::less<> incorrectly when defining a custom comparator.
Priority queues don't iterate like normal data containers, so modifying them during a traversal (iteration) is not possible.
std::priority_queue by default uses std::vector as the container. Changing the container improperly may cause compilation errors.
| Feature | Ordinary Queue | Priority Queue |
|---|---|---|
| Order | FIFO (First-In-First-Out) | Elements are ordered by priority (default: max-heap) |
| Insertion | Inserts elements at the back | Inserts elements and arranges them based on priority |
| Removal | Removes elements from the front | Removes the highest-priority element first |
| Access | front() returns the first element | top() returns the highest-priority element |
| Uses | Used when order of arrival matters (e.g., task scheduling, queue at a bank) | Used when priority matters (e.g., Dijkstra's algorithm, Huffman coding) |
| Implementation | Uses a std::deque or std::list | Uses a heap (by default, max-heap with std::vector) |
| Time Complexity | O(1) for push() and pop() | O(log N) for push() and pop() (because of heap operations) |
#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;
}
#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.
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.
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.
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.
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.
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.
Priority queues are used in diverse fields like hospitals, operating systems, flight reservations, etc.
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.
A priority queue in Dijkstra's algorithm helps efficiently select the node with the smallest distance, speeding up the shortest path calculation.
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.
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().
Source: NxtWave - CCBP Blog
Original URL: https://www.ccbp.in/blog/articles/priority-queue-in-cpp