Custom Comparator for Priority Queue

STL: template <class T, class Container = vector, class Compare = less<typename Container::value_type> > class priority_queue; i.e. the custom comparator for a priority queue is declared in a compare class by overloading the function call operator.

CODE:

class compare{
    bool operator()(pair<int,int> below,pair<int,int> above){
        //return FALSE:requires swap
        //basically we write the condition which is ideal
        if(below.first==above.first){
            reteurn below.second<above.second;//maxheap=>below should be smaller
        }
        return below.first>above.first;//minheap=>below should be larger
    }  
};
void solve(){
    priority_queue<pair<int,int>,vector<int>,compare> pq;
    for(int i=0;i<3;i++){
        pq.push({1,i});
    }
    for(int i=0;i<3;i++){
        pq.push({2,i});
    }
    cout<<"we are designing the custom comparator such that its minheap acc to the first element and in case first element is equal in some elements then its a maxheap as per the second element"<<endl;
    while(!pq.empty()){
        cout<<"("<<pq.top().first<<","<<pq.top()<<")"<<endl;
        pq.pop();
    }
}

OUTPUT:

we are designing the custom comparator such that its minheap acc to the first element and in case first element is equal in some elements then its a maxheap as per the second element:
(1,2)
(1,1)
(1,0)
(2,2)
(2,1)
(2,0)

You can practice this question to implement this concept yourself: https://leetcode.com/problems/top-k-frequent-words/description/

Custom Comparator for Sorting

The jist of building the custom comparator function:

• return FALSE: if swap required i.e. before element is actually supposed to be after
• return TRUE: in case order is correct

Method 1: Lambda function

void solve(){
    vector<pair<int,int>> vec1;
    vector<pair<int,int>> vec2;
    for(int i=1;i<=4;i++){
        vec1.push_back(make_pair(i,5-i+1));
        vec2.push_back(make_pair(i,5-i+1));
    }
    for(int i=1;i<=4;i++){
        vec1.push_back({1,i});
        vec2.push_back({1,i});
    }
    //default sort()
    cout<<"default sort: ascending according to both ele.first and ele.second: "<<endl;
    sort(vec1.begin(),vec1.end());
    for(auto ele:vec1){
        cout<<"("<<ele.first<<","<<ele.second<<");";
    }
    cout<<endl;
    //custom sort()
    cout<<"custom sort: descending according to  ele.first and ascending acc to ele.second: "<<endl;
    sort(vec2.begin(),vec2.end(),[&](pair<int,int> before,pair<int,int> after){
        //return FALSE: if swap required i.e. before ele is actually supposed to be after
        //return TRUE: in case order is correct
        if(before.first==after.first){
            return before.second<after.second;
            //if before.second is smaller it should come earlier on(ascending order)
        }
        return before.first>after.first;
        //before.first is bigger it should come earlier on(desc order)
    });
    for(auto ele:vec2){
        cout<<"("<<ele.first<<","<<ele.second<<");";
    }
    cout<<endl;
    
}

Your Output

default sort: ascending according to both ele.first and ele.second: (1,1);(1,2);(1,3);(1,4);(1,5);(2,4);(3,3);(4,2); custom sort: descending according to ele.first and ascending acc to ele.second: (4,2);(3,3);(2,4);(1,1);(1,2);(1,3);(1,4);(1,5);

Method 2: Separately defined function

static bool cmp(pair<int,int> before,pair<int,int> after){
        //return FALSE: if swap required i.e. before ele is actually supposed to be after
        //return TRUE: in case order is correct
        if(before.first==after.first){
            return before.second<after.second;
            //if before.second is smaller it should come earlier on(ascending order)
        }
        return before.first>after.first;
        //before.first is bigger it should come earlier on(desc order)
}
void solve(){
        //......
        sort(vec2.begin(),vec2.end(),cmp);
        //.......
}