如何做一个高效的优先更新在STL符?

StackOverflow https://stackoverflow.com/questions/649640

  •  19-08-2019
  •  | 
  •  

题

我有一个符的一些对象：

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

我实施这种方式，因为我是在种匆忙的时候，这是最快的事情我可以做的，我可以肯定它会的工作确定。必须有一个更好的办法比，这虽然。真的是我想要的是一种方法：

  • 提取出的实例有所改变的优先权，并插入一个新的新的优先价值
  • 更新的实例有所改变的优先级以及随后更新的队列，以便它是正确的排序

什么是最好的方式做到这一点？

有帮助吗？

解决方案

我认为你的运气与标准的优先权排队因为你不可能获得的潜在的双端/矢量/清单或什么的。你需要去实现你自己的-这并不难。

其他提示

我可以建议2的选择，以解决的问题，虽然没有执行一个真正更新。

  1. 使用 priority_queue 和推动元件，每一次你想到更新。接受这样的事实，你会拥有无用的项目在队列中。当出现的最高值，检查其中是否包含的新数值。如果不是，忽略它和流行的下一步。

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

  2. 使用 set.它也是排，以便能够提取的最大素数的时间。你也能去除过时的元件之前插入一次。因此仍然没有更新的操作可能的，但除去和重返社会是可行的。

看起来像的复杂性，这两种方法是相同的。

最直接的方式这样做STL(我知道)是删除该项，更新其优先权，然后重新插入它。这样做是相当缓慢的使用标准::符，但是你可以做同样的事情与std::置。不幸的是你必须注意不要改变的优先对象时，它是在所设定的。

我已经实施了一mutable_priority_queue类基于粘合在一起的一种标准::基于(优先权的价值映射)和性传播疾病:：地图(用于价值的优先级映射)，允许你插入/删除的项目，以及更新现有数值在对数时间。你可以得到代码和如何使用它 在这里，

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

我已经实施了一个高性能的可更新的优先排队以及由它提供 上。.

你这是怎么通常会使用：

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.

该集的方法可以更快的速度的时候做了很多新几基节点。这也是在那里使用我的图书馆将为您带来最大的改善。

你可能想看一看 replace_if 有一个例子 在这里，.

不幸的是你无法更新值在符.符不提供这样的接口。

我想你最好用 set 作为Jarekczek所述或使用 这个解决方案(使用make_heap).

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top