Configurable Priority Queues for coding interview problems (in C++)
Usually we need to use priority queues in greedy solutions. In this post we learn how to make custom priority queue that supports int, double, pairs.
What is min-heap and max-heap?
Usually, priority queues are 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 the first element
// max heap by first element
priority_queue<pair<int,int>> pq;
- Min heap by the first element
// min-heap by first element
priority_queue<pair<int,int>, vector<pair<int,int>, greater<int,int>> pq;
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;
struct cmp {
bool operator()( pair<int, int> a, pair<int, int> b){
// a.second > b,second -> min-heap wiht second value
return a.second > b.second;
}
};
priority_queue<pair<int,int>, vector<pair<int,int> >, cmp > p;
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)