Home > OS >  How can I create a priority queue that stores pairs in ascending order?
How can I create a priority queue that stores pairs in ascending order?

Time:04-10

I need to create a queue that stores pairs of integers in ascending order by their first value.

Say I have the following queue:

0 10
0 10 
1 10 
2 10 
30 10

If I try to create a priority queue with these values, it's just going to store the pairs by descending order, starting with 30 all the way to 0.

Is there a way to sort the queue or to just set the order in the declaration?

I'm trying to do:

priority_queue<pair<int, int>> queue;

for(int i=0; i<n; i  ){
    cin>>t>>d;
    queue.push(make_pair(t, d));
}

CodePudding user response:

For priority_queue, the largest element is at the front of the queue.

Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.

You could use std::greater<pair<int,int>> as custom comparator or your own comparator as well to have a custom ordering. This will put the smallest element at the front of the queue.

priority_queue<pair<int, int>, std::vector<pair<int,int>>, std::greater<pair<int,int>>> q;
  • Related