41

我有一些对象的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

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

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

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

4

7 回答 7

61

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

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

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

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

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

于 2012-12-23T08:56:08.610 回答
9

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

于 2009-03-16T09:09:38.583 回答
6

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

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

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

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

然而，当在少数基本节点上进行大量更新时，set 方法可能会更快。这也是使用我的库可以为您带来最大改进的地方。

于 2018-12-09T23:53:40.013 回答
5

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

于 2010-07-20T20:19:33.210 回答
4

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

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

于 2010-02-06T21:34:20.440 回答
0

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

于 2009-03-16T08:46:50.617 回答
0

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

我认为您最好使用setJarekczek 所说的或使用此解决方案（使用 make_heap）。

于 2017-01-02T01:06:44.577 回答