1
\$\begingroup\$

I want a priority queue such that first it should be done on basis of first element (increasing order)and when clash occurs then on basis of second element(decreasing order). I came up with the following code :

#include<bits/stdc++.h>
using namespace std;


struct Compare {
    constexpr bool operator()(pair<int, int> const & a,
                              pair<int, int> const & b) const noexcept
    { return a.first > b.first && a.second<b.second; }
};

int main()
{
    priority_queue<pair<int,int>,
                   std::vector<pair<int,int> >,
                   Compare> Q;
    int n;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        ll a,b;
        cin>>a>>b;
        Q.push(make_pair(a,b));
    }

    for(ll i=0;i<n;i++)
    {
        pair<ll,ll> m;
        m=Q.top();
        cout<<m.first<<" "<<m.second<<"\n";
        Q.pop();
    }
}

For eg - If I have following pairs : (1,10),(1,7),(1,5),(2,8),(2,6),(3,5),(3,9)

My output should be as follows on calling Q.top() and Q.pop()

1 10
1 7
1 5
2 6
2 8
3 5
3 9

But instead I'm getting the following output:

1 10
1 5
3 9
1 7
2 8
2 6
3 5

Can someone help me out ?

\$\endgroup\$
2
\$\begingroup\$

This test is wrong:

return a.first > b.first && a.second<b.second;

Try:

return a.first > b.first || (a.first == b.first && a.second < b.second)

Some other things

This is not a legal header

#include<bits/stdc++.h>

Remove this immediately your code is invalid with it there.

Never do this:

using namespace std;

Its a bad habit that will cause you problems in real code. Always pre-fix things from the standard library with std:: (Its short for a reason).

see: https://stackoverflow.com/q/1452721/14065

Use menaingful variable names.

Names like i n m have no meaning. Also when you have longer code searching the source for them will turn up a lot of false negatives thus making it harder to keep your code working.

Prefer prefix ++ over the postfix version.

    for(int i=0;i<n;i++)

    for(int loop = 0; loop < inputElementCount; ++loop)

A bit of white space makes things easier to read.

        cin>>a>>b;

        // Why not
        std::cin >> value1 >> value2;

When poping from a queue you should check its not empty not assume it has a particular size:

for(;!queue.empty(); queue.pop())
{
    auto const& item = queue.top();
    std::cout << item.first << " " << item.second << "\n";
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for these suggestions. I will keep these points in mind next time ! \$\endgroup\$ – Bash Jul 9 '17 at 19:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.