如何在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. 使用set.它也是排序的,因此您可以在对数时间内提取最大元素.您还可以在再次插入之前删除过时的元素.因此仍然无法进行更新操作,但删除和重新插入是可行的.

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

Answer 2

我认为你对标准优先级队列运气不好,因为你无法获得底层的deque/vector/list或其他什么.你需要实现自己的 - 它并不难.

Answer 3

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

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

Answer 4

适当的数据结构称为"Fibonacci Heap".但是你需要自己实现它.插入/更新是O(1)ExtractMin是O(logn)

Answer 5

我已经实现了一个高性能的可更新优先级队列，并使其在 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 时通常使用它的原因。

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