Home » C++ STL

C++ STL | User-defined comparator for priority queue

User-defined comparator for priority queue in C++ STL: Learn to create min heap using priority_queue, define your comparator for priority queue, etc with examples.
Submitted by Radib Kar, on July 07, 2020

In this article, we are going to see how to write your comparator function for priority queue in C++ STL using the lambda function. This is going to help you certainly to use priority queue more widely when you may have skipped thinking about how you can create a priority queue of your data type, or using your comparator.

Default priority queue in C++ STL

Syntax for default priority queue in C++ STL is:

priority_queue<int> pq;

By default the above priority queue works as the max heap, i.e., the maximum value from will come on the top and so on. So, if we pop and print we will have a sorted list in descending order.

Create min heap using priority_queue STL

We can use greater<int> class to define a min heap

Syntax

The syntax would be:

priority_queue<int,vector<int>,greater<int>> pq;

Where, vector<int> works as container and greater<int> as  comparator class,

Define your own comparator for priority queue

You may have often come to a situation when you need to use a priority queue, but your datatype is something else that can't be compared by default (using '<' operator what is used by default). In such cases, we need to declare our comparator function.

We can use the lambda function for that.

For example,

Say we need to compare the below object,

student{
    int roll
    int marks
};

And the comparison rule is if any two students have the same marks, then they would be sorted based on roll(whose roll comes first will have priority), otherwise, the student having more marks has more priority.

How would we define the comparator for the above?

Below is the use of lambda function which will be our comparator

Syntax

The syntax is:

auto it=[](student a, student b){
    //comparison logic
    if(a.marks>b.marks)
        return false;
    else if(a.marks<b.marks)
        return true
    else //when marks are same
    if a.roll<b.roll
        return false
    else
        return true
}; 

The above is the lambda comparator function which takes as argument two data member and use the logic two compare, false means the current position is okay, that is no swap required, true means swap required.

Priority queue declaration

Now, the priority queue will be declared as:

priority_queue<student, vector<student>, decltype(it)> pq(it);

Where it is our comparator function. One thing to notice that the comparator function is passed as constructor too.

So whenever you add an item to the priority queue,

It does necessary swaps according to our user-defined logic and places the items in an order.

Example

Say we have 5 students with below data,

Roll	Marks
1	65
2	78
3	87
4	65
5	78

So inserting the first student data in the priority queue.

Since no other member.

Priority queue will be now,

1	65

So inserting the second student data in the priority queue.

Now as per our comparator there will be swap.

And thus, the priority queue will be now,

2	78
1	65

So, inserting the third student data in the priority queue.

Now, as per our comparator, there will be a swap.

And thus, the priority queue will be now,

3	87
2	78
1	65

So, inserting the fourth student data in the priority queue.

And thus as per our comparator, the priority queue will be now,

3	87
2	78
1	65
4	65

So, inserting the fifth student data in the priority queue.

And thus as per our comparator, the priority queue will be now,

3	87
2	78
5	78
1	65
4	65

So after popping we will get student list as,

3 87
2 78
5 78
1 65
4 65

C++ implementation for user-defined comparator for priority queue

#include <bits/stdc++.h>
using namespace std;

class student {
public:
    int roll;
    int marks;
    student()
    {
        roll = 0;
        marks = 0;
    }
};

void sort_students(vector<student> arr)
{
    //comparator lambda function
    auto comp = [](student a, student b) {
        //comparison logic
        if (a.marks > b.marks)
            return false;
        else if (a.marks < b.marks)
            return true;
        else { // when marks are same
            if (a.roll < b.roll) {
                return false;
            }
            else
                return true;
        }
    };

    priority_queue<student, vector<student>, decltype(comp)> pq(comp);

    for (auto& ij : arr) {
        pq.push(ij);
    }
    //printing the sorted list
    cout << "roll marks\n";
    while (!pq.empty()) {
        cout << pq.top().roll << " " << pq.top().marks << endl;
        pq.pop();
    }
}

int main()
{

    int n;
    
    cout << "Enter number of students\n";
    cin >> n;
    
    vector<student> arr(n);
    cout << "Enter roll and marks for each student\n";
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        arr[i].roll = x;
        arr[i].marks = y;
    }
    
    cout << "sorting students according to marks and roll no: \n";
    
    sort_students(arr);
    
    return 0;
}

Output

Enter number of students
5
Enter roll and marks for each student
1 65
2 78
3 87
4 65
5 78
sorting students according to marks and roll no: 
roll marks
3 87
2 78
5 78
1 65
4 65