Evang's blog

Minimum priority queue in C++
By Evang, history, 4 years ago, In English

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?

  • Vote: I like it
  • +41
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    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.

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

      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.

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

        Oh, that's slightly inefficient than set I guess. Overall , we are storing more elements, right?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          The complexity is the same for both. But priority_queue gives better runtime than set actually.

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

Just use priority_queue and use negative values for min heap.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

→ Reply