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/