apjcoder123's blog

By apjcoder123, history, 2 years ago, In English

I am trying to learn about custom comparators in priority queue. however, i am unable to get the expected behaviour. I have wrote two custom comparators in the below code one for a vector and the other for a priority queue and the logic is same for both the comparators. how the output seems to be opposite, can anyone tell me the reason for this, any help will be appreciated.

In my thinking the output given by the priority queue should be same as the vector but it isn't.

Actual Ouput:

Vector: 1 6 2 5 2 4

Priority Queue: 2 4 2 5 1 6

Expected Output:

Vector: 1 6 2 5 2 4

Priority Queue: 1 6 2 5 2 4

struct cmp1 {
    bool operator()(pii const& a,pii const& b)
    {
        if(a.first==b.first) return a.second>b.second;
        return a.first<b.first;
    }
};

bool cmp2(pii const& a,pii const& b)
{
    if(a.first==b.first) return a.second>b.second;
    return a.first<b.first;
}

int main()
{
    priority_queue<pii,vector<pii>,cmp1> cust_heap;
    cust_heap.push({1,6});
    cust_heap.push({2,4});
    cust_heap.push({2,5});
    
    vector<pii> v;
    v.push_back({1,6});
    v.push_back({2,4});
    v.push_back({2,5});
    
    sort(v.begin(),v.end(),cmp2);
    
    cout<<"Vector: "<<'\n';
    
    for(auto x:v) cout<<x.first<<" "<<x.second<<'\n';
    
    cout<<'\n';
    
    cout<<"Priority Queue: "<<'\n';
    
    while(!cust_heap.empty())
    {
        int freq=cust_heap.top().first;
        int element=cust_heap.top().second;
        cust_heap.pop();
        cout<<freq<<" "<<element<<'\n';
    }
    
    cout<<'\n';
    
    return 0;
}
  • Vote: I like it
  • +7
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

vector uses the compare to sort the smaller elements to the front, but pq uses the comparator to place larger elements at the top of the heap, bc pq is naturally a max heap. if u use the greater param in vector and pq u get different results as well.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

There is another way, You can do everything without making any comparators. just add negative of values to your vector and priority queue. Now on using sort your vector will be sorted in descending manner if you will not consider the negative sign.
Example :--> vector v={1,6,2,5,2,4}
make it :--> vector v={-1,-6,-2,-5,-2,-4} and then use sort
result after sorting :--> {-6,-5,-4,-2,-2,-1} , now just multiply these values with -1 and you will get what you desired. {6,5,4,2,2,1}.

You can use this trick everywhere instead of making a comparator function.