代码之家 › 专栏 › 技术社区 › 1800 INFORMATION

如何在STL优先级队列中进行有效的优先级更新?

priority-queue stl c++

1800 INFORMATION · 技术社区 · 17 年前

我有一些对象的优先队列:

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

我这样实现它是因为当时我有点匆忙,这是我能做的最快的事情,我可以肯定它会正常工作。但总有比这更好的方法。我真正想要的是一种方法:

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

最好的方法是什么?

7 回复 | 直到 7 年前

anon 17 年前

我认为您在标准优先级队列方面不太走运,因为您无法获得底层deque/vector/list或其他什么。你需要实现你自己的-这并不难。

Jarekczek 13 年前

我可以建议两个选项来解决这个问题,尽管它们都没有执行真正的更新。

使用 priority_queue 每次您想要更新它时都会推送元素。接受这样一个事实:队列中会有无用的条目。弹出最高值时,检查它是否包含最新值。如果没有,忽略它并弹出下一个。

这样就可以延迟删除更新的元素,直到它到达顶部。我注意到这种方法正被顶级程序员用来实现Dijkstra算法。
使用 set . 它也被排序,这样您就可以在对数时间内提取最大的元素。您还可以在再次插入之前删除过时的元素。所以仍然没有更新操作可能,但删除和重新插入是可行的。

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

James Gregosn 16 年前

使用STL(我知道)进行此操作的最简单方法是删除条目,更新其优先级,然后重新插入。使用std::priority_队列执行此操作非常缓慢,但是可以使用std::set执行相同的操作。不幸的是,当对象在集合中时,必须小心不要更改其优先级。

我已经实现了一个基于可变优先级的队列类,将一个std::multimap(用于优先级到值的映射)和一个std::map(用于值到优先级的映射)粘合在一起,它允许您插入/删除项,以及以对数时间更新现有值。您可以得到代码和如何使用它的示例 here

Nima 15 年前

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

Ten 7 年前

我实现了一个高性能的可更新优先级队列并使其可用 on 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_元素),需要定期更新,而 STL::优先级队列 是一个尽可能纯净和快速的二进制堆。这就是为什么它通常在实现dijkstra时使用的原因。

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

dubnde 17 年前

你可能想看看 replace_if 举个例子 here .

Community Mohan Dere 9 年前

很遗憾,您无法更新优先级队列中的值。优先级队列不提供此类接口。

我想你最好用一下 set 如Jarekczek所说或使用 this solution (使用make_heap)。