Configurable Priority Queues for coding interview problems (in C++)

Configurable Priority Queues for coding interview problems (in C++)
Photo by Zichao Zhang / Unsplash

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:

OperationAPITime complexity
Insertion of elementpq.push(x)O(logN)
Removing an elementpq.pop()O(logN)
Finding the top of priority queuepq.top()O(1)
Size of priority queuepq.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