meiniak's blog

Priority Queue Of product of pair

By meiniak, history, 5 years ago, In English

I just want to use priority queue with pair of integers such that it stores the maximum product of 2 numbers in descending order . How can i use it in C++ .

For Eg : —

2 5

5 10

3 6

will be save in priority queue as

5 10

3 6

2 5

and if a clash happen , then the first element should be prefer .

Also I was solving this problem using priority queue but getting WA at case 30 , strange RUNTIME error for comparison but it passes using vector of pairs . I just found on the net on how to write custom comparison function for priority queue . Is there any other method without using class or struct .

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Instead of defining class / struct expilictly, you can use lambda expression as a comparator: example

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me what's wrong with my this solution . It is same as my accepted solution using vector of pairs .

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You need to modify the condition inside the while loop from while(n!=0) to while(n!=0 && !pq.empty()), because there can be the situation when the burglar can steal more matchboxes than there is in the warehouse.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Should't the sign should be changed i.e > . I know it will give opposite result . But as far as i know that if we have to keep 1'st preference than we should return true in c++ ? . Here is the same code with opposite sign implemented on vector of pairs . link

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Documentation
      Note that the default comparator is std::less<T> but as stated in the documentation, std::priority_queue "provides constant time lookup of the largest (by default) element".
      So for std::vector you are right, the sign needs to be changed, but for std::priority_queue it shouldn't because the top element of the priority queue is the greatest one (with respect to your comparison function). For an instance, if your comparison function is p1.first * p1.second < p2.first * p2.second then the top element of the std::priority_queue would be one of the elements with greatest product. And if you need to choose among of them the one having the greatest first value you need to add this condition to the comparator: || (p1.first * p1.second == p2.first * p2.second && p1.first < p2.first).

      → Reply