Configurable Priority Queues for coding interview problems (in C++)
Priority queues are often used in greedy solutions. In this post, we learn how to make a custom priority queue that supports int, double, and pairs.
What is min-heap and max-heap?
Priority queues are often used in greedy solutions in Leetcode problems and OAs. Priority queues allow for O(log N) insertion into a data structure which keeps items sorted according to a logic defined by the programmer.
Max-heap = descending order (greatest element at top)
Min-heap = ascending order (smallest element at top)
Simple Priority Queue
Max Heap
priority_queue<int> pq → Stores elements in decreasing value.
Time complexity analysis:
| Operation | API | Time complexity |
| Insertion of element | pq.push(x) | O(logN) |
| Removing an element | pq.pop() | O(logN) |
| Finding the top of priority queue | pq.top() | O(1) |
| Size of priority queue | pq.size() | O(1) |
Min Heap
priority_queue<int, vector<int>, greater<int>> pq → Stores elements in increasing value.
Time complexity analysis:
Same as max-heap.
Do priority queues work for double?
Yes!
Same behavior as int!
Pair of elements
In many problems, we have to order the elements according to some value (for example, cost, price, weight, or any other property), and we also want to identify which element it represents (using an id, or index).
In this case, we need to use a priority queue of pairs where elements are ordered according to one property and the other property is used merely for identification.
In this case, we can use the following formats:
Ordering by the first element
// max heap by first element
priority_queue<pair<int,int>> pq;
Max heap by the first element
// min-heap by first element
priority_queue<pair<int,int>, vector<pair<int,int>, greater<int,int>> pq;
Min heap by the first element
Ordering by the second element
For ordering by the second element, we have to write a custom comparator method that contains the comparison logic of the priority queue.
Custom comparator function
We can notice that (a,b) ⇒ a<b yields ascending order.
struct cmp {
bool operator()( pair<int, int> a, pair<int, int> b){
// a.second < b.second -> max-heap with second value
return a.second < b.second;
}
};
priority_queue<pair<int,int>, vector<pair<int,int> >, cmp > p;
Max heap for pairs sorted by the second value
struct cmp {
bool operator()( pair<int, int> a, pair<int, int> b){
// a.second > b,second -> min-heap with second value
return a.second > b.second;
}
};
priority_queue<pair<int,int>, vector<pair<int,int> >, cmp > p;
Min heap for pairs sorted by the second value
Priority Queue for structs
Defining a priority queue for the Point struct, which stores them in order of increasing x*y.
struct Point{
int x;
int y;
Point(int xx, int yy){
x = xx;
y = yy;
}
};
struct Compare{
bool operator()(Point a, Point b){
// a.second > b,second -> min-heap wiht second value
return a.x * a.y > b.x * b.y;
}
};
// defining pq
priority_queue<Point, vector<Point>, Compare> pq;
// (1,1) will be before (1,10)Priority queue using custom logic for structs
