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

Update key operation in a priority queue
Автор Scandium, 22 месяца назад, По-английски

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?

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This looks good, thanks.

    → Ответить
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

→ Ответить