Custom Comparators for Priority Queue

Revision en1, by anveshgandotra_, 2025-01-16 18:04:45

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/

Tags custom comparator, priority queue, cpp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English anveshgandotra_ 2025-01-16 18:04:45 1677 Initial revision (published)