anveshgandotra_'s blog

By anveshgandotra_, history, 7 hours ago, In English

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/

  • Vote: I like it
  • +4
  • Vote: I do not like it