C++ 如何在 STL priority_queue 中进行高效的优先级更新？

How to do an efficient priority update in STL priority_queue?

提问by 1800 INFORMATION

I have a priority_queue of some object:

我有某个对象的priority_queue：

typedef priority_queue<Object> Queue;
Queue queue;

From time to time, the priority of one of the objects may change - I need to be able to update the priority of that object in the queue in an efficient way. Currently I am using this method which works but seems inefficient:

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

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

I implemented it this way because I was in kind of a hurry at the time and this was the quickest thing I could do that I could be sure it would work ok. There has to be a better way than this though. Really what I want is a way to either:

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

• extract out the instance with the changed priority and insert a new one with the new priority value
• update the instance with the changed priority and then update the queue so that it is correctly sorted

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

What is the best way to do this?

做这个的最好方式是什么？

采纳答案by 1800 INFORMATION

I think you are out of luck with standard priority queue because you can't get at the underlying deque/vector/list or whatever. You need to implement your own - it's not that hard.

我认为您对标准优先级队列不走运，因为您无法获得底层双端队列/向量/列表或其他任何内容。您需要实现自己的 - 这并不难。

回答by Jarekczek

I can suggest 2 choices to solve the problem, although neither performs a real update.

我可以建议 2 种选择来解决问题，尽管两者都没有进行真正的更新。

1. Use the priority_queueand push element each time you would like to update it. Accept the fact that you will have useless entries in the queue. When popping the top value, check if it contains the up-to-date value. If not, ignore it and pop the next.

   This way you delay the removal of the updated element until it comes to the top. I noticed this approach being used by top programmers realizing Dijkstra algorithm.

2. Use set. It is also sorted so you are able to extract the greatest element in logarithmic time. You are also able to remove the outdated element before inserting it again. So still no update operation possible, but removal and reinsertion is doable.

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

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

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

Seems like the complexity of both approaches is the same.

似乎两种方法的复杂性是相同的。

回答by Nima

The appropriate data structure is called "Fibonacci Heap". But you need to implement it yourself. Insert/Updates are O(1) ExtractMin is O(logn)

适当的数据结构称为“斐波那契堆”。但是你需要自己实现它。插入/更新是 O(1) ExtractMin 是 O(logn)

回答by James Gregosn

The most straightforward way to do this with STL (that I know) is to remove the entry, update its priority and then reinsert it. Doing this is quite slow using std::priority_queue, however you can do the same thing with std::set. Unfortunately you have to be careful to not change the priority of an object when it is in the set.

使用 STL（我知道）执行此操作的最直接方法是删除条目，更新其优先级，然后重新插入。使用 std::priority_queue 执行此操作非常慢，但是您可以使用 std::set 执行相同的操作。不幸的是，当一个对象在集合中时，你必须小心不要改变它的优先级。

I have implemented a mutable_priority_queue class based gluing together an std::multimap (for priority to value mapping) and an std::map (for value to priority mapping) that allows you to insert/remove items as well as update existing values in logarithmic time. You can get the code and an example of how to use it here

我已经实现了一个基于 mutable_priority_queue 类的将 std::multimap（用于值映射的优先级）和 std::map（用于值到优先级映射）粘合在一起，它允许您插入/删除项目以及更新对数中的现有值时间。您可以在此处获取代码以及如何使用它的示例

回答by Ten

I have implemented a high-performance updatable priority queue and made it available on github.

我已经实现了一个高性能的可更新优先级队列，并使其在 github 上可用。

This is how you would typically use it :

这是您通常使用它的方式：

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

To complement Jarekczek's answer, if indeed both the setand "pure heap with useless entries" approaches have the same complexity, the stl::setversion typically performs much slower than the stl::priority_queueversion due to the fact that it is implemented with red-black trees that only guarantee their depth to be lower than 2*log_2(n_elements) and require regular updates, while stl::priority_queueis an as pure and fast binary heap as possible. This is why it is typically used when implementing Dijkstra.

为了补充 Jarekczek 的答案，如果确实set和“带有无用条目的纯堆”方法具有相同的复杂性，则该stl::set版本的执行速度通常比stl::priority_queue版本慢得多，因为它是用红黑树实现的，仅保证它们的深度低于 2*log_2(n_elements) 并且需要定期更新，同时stl::priority_queue是尽可能纯净和快速的二进制堆。这就是为什么在实现 Dijkstra 时通常使用它的原因。

The set approach may however be faster when making a lot of updates on few base nodes. This is also where using my library would bring you the most improvement.

然而，当在几个基本节点上进行大量更新时，集合方法可能会更快。这也是使用我的库会给你带来最大改进的地方。

回答by Yeongjin Choi

Unfortunately you cannot update value in priority_queue. priority_queue does not offer such interface.

不幸的是，您无法更新 priority_queue 中的值。priority_queue 不提供这样的接口。

I think you'd better use setas Jarekczek said or use this solution(using make_heap).

我认为您最set好像 Jarekczek 所说的那样使用或使用此解决方案（使用 make_heap）。

回答by dubnde

You may want to have a look at replace_ifwith an example here.

你可能想看看这里replace_if的例子。