Scandium's blog

Update key operation in a priority queue
By Scandium, 3 years 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

»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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