STL Quiz priority_queue

#1

Q11. stl priority_queue user defined comparator
What will be the output of following C++ code?

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
struct Compare
{
    bool operator()(pi const & a, pi const & b)
    {
         if(a.second < b.second)
         {
            return true;
         }
         else if(a.second > b.second)
         {
             return false;
         }
         else
         {
             if(a.first > b.first)
             {
                 return true;
             }
             return false;
         }
    }
};
int main()
{
    priority_queue<pi , vector<pi>, Compare>q;
    q.push({1, 5});
    q.push({5, 15});
    q.push({7, 15});
    q.push({10, 2});
    q.push({1, 10});
    cout<<q.top().first<<" "<<q.top().second<<endl;
    return 0;
}

1 10

7 15

5 15

10 2

My answer is 10 2

#2

@Kinjal no the correct answer is 5 15, you can run the code and verify.
Remeber that comparator for priority queues work slightly different than comparator for the sorting of a linear structure like an array

#3

yes, I need to know the internal comparison. How it compares elements?

#4

@Kinjal watch the videos on implementation of heaps…if i remember sir has explained there

#5

It’s in STL course so not told. Can’t you say how compare() works in this program with given elements?

#6

@Kinjal
it works quite opposite to the other comparators…if you want max heap then use a < b and if you want min heap then use a > b
now in this question

if(a.second < b.second)
{
    return true;
}
else if(a.second > b.second)
{
    return false;
}

this means that if second element is not equal, the pairs will be sorted in descending order of the pair.second. This means that the pairs will be arranges like (just showing pair.second here) {15,15,10,5,2}
if the second values happen to be equal, then,

if(a.first > b.first)
{
    return true;
}
return false;

this means that the pairs will be arranges in acsending order according to pair.first, which is {1,1,5,7,10}

Now, list of all pairs:

{1, 5}
{5, 15}
{7, 15}
{10,2}
{1,10}

firstly arranged according to pair.second (in dec order)

{7,15}
{5,15}
{1,10}
{1,5}
{10,2}

And now, in case pair.second is equal, arrange them in inc order acc to pair.first

{5,15}
{7,15}
{1,10}
{1,5}
{10,2}

as you can see, 5 15 will be on top.

#7

Ohhh. Got it. I think, same kinda implementation occurs in sort(a,a+n,compare) functions too. When
compare(int a, int b){ return a>b;} comparator is defined then,
Actually it will give ascending order of the elements.

So, I guess it’s same for all comparators.

#8

@Kinjal

no, if you return a>b (for an array) it will return descending order (decreasing order) of elements

#9

yeah, you’re right.

So, it will act opposite only for priority_queue, right!

#10

@Kinjal yes that’s what i stated earlier also.

#11

And, I confirmed it. Because it’s confusing. If you see in lower_bound and upper_bound it will work very differently.

#12

@Kinjal is it clear now?

#13

Do you think, lower_bound and upper_bound comparator function will work same way?

#14

Yes…It’s clear that priority_queue act differently. Thanks. You are awesome.

#15

@Kinjal lower_bound and upper_bound functions have completely different purpose…they are not used for sorting.

#16

No, I was talking about comparator function passed in lower_bound and upper_bound functions. Anyway, NEVER MIND!

#17

@Kinjal even their comparator function works differently… dont get confused betweent the 2. One is for searching one is for sorting

#18

See, what comparator function does is that just change the comparison between two numbers or objects so if it’s used in sorting or priority_queue or lower_bound or upper_bound, it doesn’t matter. Only different behavior is implementation. But, anyway I understood what you’re saying.

1 Like