Блог пользователя Evang

Minimum priority queue in C++
Автор Evang, история, 5 лет назад, По-английски

Hello Codeforces!

I've seen people using negative edges when creating a priority queue because writing a minimum is simply too tedious. And, I gotta say, I agree with them! Look at this code when you have to declare a min heap for a pair of ints:

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

That simply is too much to write! However, there is a simple solution. Just include this somewhere near the top of your code:

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

Now you can declare a min heap of pairs of ints by writing:

min_heap<pair<int, int>> q;

To me, that is more clear and concise, and less to type! Are there any other reasons that some people might create a min heap by negating edge weights instead of writing that block of code at the top?

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

When I perform dijkstra.I always use prioroty_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > > pq;

→ Ответить
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Just use priority_queue and use negative values for min heap.

→ Ответить
»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +2 Проголосовать: не нравится

I do this, this method allows other comparisons rather than only min / max. For example, if you want to prioritize the pair of ints with smaller sum, 

struct cmp {
    bool operator() (pair<int, int> a, pair<int, int> b) {
         return a.ff+a.ss > b.ff+b.ss;
    }
};
priority_queue<pair<int, int> , vector<pair<int, int>>, cmp> pq;

and pq always spits out the pair that has the smallest sum.

→ Ответить