c++ - 如何在 STL priority_queue 中进行有效的优先级更新？

Question

我有一些对象的priority_queue:

typedef priority_queue<Object> Queue;
Queue queue;

有时，其中一个对象的优先级可能会发生变化 - 我需要能够以有效的方式更新队列中该对象的优先级。目前我正在使用这种有效但似乎效率低下的方法:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

我以这种方式实现它是因为我当时有点着急，这是我能做的最快的事情，我可以肯定它会正常工作。不过，必须有比这更好的方法。我真正想要的是一种方法:

• 提取具有更改优先级的实例并插入具有新优先级值的新实例
• 使用更改后的优先级更新实例，然后更新队列以使其正确排序

最好的方法是什么？

Answer 1

我可以建议 2 种选择来解决问题，尽管它们都不执行真正的更新。

1. 每次您想更新它时，使用 priority_queue 和 push 元素。接受这样一个事实，即队列中将有无用的条目。弹出顶部值时，检查它是否包含最新值。如果没有，忽略它并弹出下一个。

   这样您可以延迟删除更新的元素，直到它到达顶部。我注意到实现 Dijkstra 算法的顶级程序员正在使用这种方法。

2. 使用设置。它也经过排序，因此您能够在对数时间内提取最大元素。您还可以在再次插入之前删除过时的元素。所以仍然无法进行更新操作，但移除和重新插入是可行的。

似乎这两种方法的复杂性是一样的。