Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Scandium's blog

Update key operation in a priority queue
By Scandium, 18 months ago, In English

I have found a couple of ways to update a key in the priority queue when I searched online. I am just wondering what way of implementation do you prefer using existing C++ STL data structures?

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just use set instead of a priority queue. It has the same functionality (keys are in sorted order), you can get first key by using *myset.begin(). And if you want to update some key called "key", then you just erase the key using, myset.erase(myset.find(key)), then add the updated version of the key — called "updated_key" — by using, myset.insert(updated_key). This is what I use when i implement dijkstra's algorithm.

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

    Also note, that they "erase", and "find" operations in a set are O(logn), while getting the beginning iterator, "myset.begin()) is only O(1). So this is quite an efficient solution.

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

    This looks good, thanks.

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

    I think you are going to make the same mistake of using set instead of multiset.

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

      Haha I see you read my blog! You are right i just made the same mistake. Thanks for pointing it out!

      → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you can also use __gnu_pbds::priority_queue: it has modify(iterator, value)

→ Reply