# 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.

**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

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

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,

*means swap required.*

**true**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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.