Priority queues are a fundamental data structure in C++ Standard Template Library (STL), especially useful when you need to efficiently manage elements with priorities. They are built upon the concept of heaps, offering quick access to the highest or lowest priority element. This article delves into priority queues, focusing on how to implement a min-heap using custom comparators in C++.
Understanding Priority Queues and Heaps
At its core, a priority queue is an abstract data type similar to a regular queue or stack, but with a twist: each element has a priority associated with it. In a priority queue, elements are served based on their priority, not their insertion order. Heaps are the data structure that typically backs priority queues, providing the efficiency they are known for.
Heaps possess these key characteristics:
- Fast Retrieval of Min/Max: Accessing the minimum (in a min-heap) or maximum (in a max-heap) element takes constant time, O(1). This is because the root of the heap always holds the extreme element.
- Efficient Insertion and Deletion: Adding or removing elements while maintaining the heap property takes logarithmic time, O(log N), where N is the number of elements.
By default, C++ std::priority_queue is implemented as a max-heap. This means it’s designed to always have the largest element at the top. However, many applications require a min-heap, where the smallest element is at the top. This is where custom comparators become essential.
Why Use a Custom Comparator for a Min Heap Priority Queue?
The standard C++ priority queue, by default, orders elements using std::less. This results in a max-heap, where the largest element is always at the top, ready to be accessed or removed. While a max-heap is useful in many scenarios, there are numerous cases where a min-heap is required. For instance, algorithms like Dijkstra’s shortest path and Huffman coding rely on efficiently retrieving the smallest element, making a min-heap priority queue the ideal choice.
To create a min-heap priority queue, you need to tell the priority queue to order elements differently – to prioritize smaller elements instead of larger ones. This is achieved using a comparator. A comparator is essentially a function or function object that defines the comparison logic between elements.
Furthermore, custom comparators are not just limited to creating min-heaps. They are crucial when dealing with:
- Complex Data Types: When your priority queue stores objects or pairs, you need to define how these complex elements should be compared. Simple ascending or descending order might not be sufficient. You might need to prioritize based on specific attributes or combinations of attributes within your objects.
- Non-Standard Ordering: You might require a priority queue that orders elements based on criteria other than simple numerical or lexicographical order. A custom comparator allows you to implement any comparison logic you need.
In essence, custom comparators provide the flexibility to tailor the behavior of your priority queue to precisely match the needs of your application, whether it’s creating a min-heap or implementing complex prioritization rules.
Implementing a Custom Comparator for a Min Heap
To use a custom comparator with std::priority_queue, you need to define a class or a function object that overloads the operator(). This operator will take two arguments of the data type stored in the priority queue and return a boolean value indicating their order.
For creating a min-heap, you can use the pre-defined comparator std::greater. Let’s see how to use both std::greater and a custom class comparator.
1. Using std::greater for Min Heap
The simplest way to create a min-heap is by using std::greater as the comparator. Here’s the syntax:
priority_queue<int, vector<int>, greater<int>> minHeap;In this declaration:
int: Specifies that the priority queue will store integers.vector<int>: Indicates that astd::vectorwill be used as the underlying container (this is the default, but explicitly stated for clarity).greater<int>: This is the crucial part.std::greater<int>is a function object (functor) that defines the “greater than” comparison. When used as a comparator inpriority_queue, it reverses the default max-heap behavior, making it a min-heap.
2. Creating a Custom Comparator Class
For more complex scenarios or for better understanding, you can create your own comparator class. Here’s the general structure:
template <typename T>
class Compare {
public:
bool operator()(const T& a, const T& b) {
// Define your comparison logic here
if (/* condition for 'a' to have higher priority than 'b' in min-heap */) {
return true; // Indicate 'a' has lower value (higher priority for min-heap)
}
return false; // Indicate 'b' has lower or equal value
}
};Explanation:
template <typename T>: Makes the comparator class generic, working with any data typeT.class Compare: The name of our custom comparator class.public: bool operator()(const T& a, const T& b): This is the overloaded function call operator. It takes two constant references (const T&) to elementsaandb.- Return Value Logic (Crucial for Min-Heap):
return true;: This is counter-intuitive at first. Returningtruemeans that the order is not correct according to the min-heap property (smaller element should be at the top). In the context ofpriority_queue, returningtruetriggers a swap, moving the smaller element up the heap. Think of it as “swap if true” to maintain the min-heap order.return false;: This means the order is correct, and no swap is needed.
Example: Custom Comparator for Pairs in a Min-Heap
Let’s consider a practical example where we want to store pairs of integers in a min-heap priority queue. We want to prioritize pairs based on the following rules:
- Primary Sorting: Sort in ascending order based on the first element of the pair. (Smaller first element = higher priority in min-heap)
- Secondary Sorting (for pairs with the same first element): Sort in descending order based on the second element of the pair. (Larger second element = higher priority when first elements are equal)
Here’s the custom comparator class to achieve this:
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
using PII = pair<int, int>; // Pair of Integers
class ComparePairs {
public:
bool operator()(const PII& below, const PII& above) {
if (below.first > above.first) {
return true; // Swap if below.first is greater (for ascending first element)
} else if (below.first == above.first && below.second < above.second) {
return true; // Swap if first elements are equal and below.second is smaller (for descending second element)
}
return false; // No swap needed
}
};And here’s how to use it with priority_queue:
int main() {
priority_queue<PII, vector<PII>, ComparePairs> ds;
ds.push({100, 11});
ds.push({100, 41});
ds.push({100, 21});
ds.push({300, 1});
ds.push({300, 2});
ds.push({1, 1});
ds.push({1, 2});
ds.push({1, 20});
cout << "The min-heap priority queue (custom comparator) is: n";
while (!ds.empty()) {
cout << ds.top().first << " " << ds.top().second << "n";
ds.pop(); // Heapify happens after pop
}
return 0;
}This code snippet demonstrates how to create a min-heap priority queue that sorts pairs according to our custom logic. The ComparePairs class dictates the ordering, ensuring the smallest pair (based on our defined criteria) is always at the top.
The min-heap priority queue (custom comparator) is:
1 20
1 2
1 1
100 41
100 21
100 11
300 2
300 1Time and Space Complexity
Time Complexity: The time complexity for push and pop operations in a priority queue (heap) is O(log K), where K is the current number of elements in the priority queue. If you perform N insertions, the total time complexity can be up to O(N log K), and in the worst case, where K is close to N, it becomes O(N log N).
Space Complexity: The space complexity is O(K), as the priority queue stores up to K elements. In the case where you store N elements, the space complexity is O(N).
Conclusion
Custom comparators are powerful tools for tailoring the behavior of C++ priority queues. They are essential for creating min-heaps and for implementing complex prioritization logic when working with custom data types or non-standard ordering requirements. By understanding how to define and use custom comparators, you can effectively leverage priority queues in a wide range of algorithms and applications.
