Evang's blog

By Evang, history, 6 weeks ago,

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

 » 6 weeks ago, # |   +5 When I perform dijkstra.I always use prioroty_queue,vector>,greater > > pq;
•  » » 6 weeks ago, # ^ |   -14 How does that work?! Dikstra requires you to modify elements which are not at the top of the heap. And pq doesn't allow that. How can you use pq for dikstra?! I have always used set.
•  » » » 6 weeks ago, # ^ |   0 Instead of modifying element inside PQ, just push the new pair. But when popping element from PQ, check if the distance matches the currently known distance. If it doesn't, then just ignore that pair.
•  » » » » 6 weeks ago, # ^ |   0 Oh, that's slightly inefficient than set I guess. Overall , we are storing more elements, right?
•  » » » » » 6 weeks ago, # ^ |   +17 The complexity is the same for both. But priority_queue gives better runtime than set actually.
 » 6 weeks ago, # |   0 Just use priority_queue and use negative values for min heap.
 » 6 weeks ago, # | ← 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 a, pair b) { return a.ff+a.ss > b.ff+b.ss; } }; priority_queue , vector>, cmp> pq; and pq always spits out the pair that has the smallest sum.