在STL优先级队列中实现decreaseKey队列C++

我试图实现Prim的算法，并且我需要为优先级队列（更新优先级队列中的键值）使用decreaseKey方法。我可以在STL优先级队列中实现吗？在STL优先级队列中实现decreaseKey队列C++

如果有帮助，这是我下面的算法：每个顶点u在图G的U至INFINITY

SET键NIL
集父
将源顶点的密钥设置为0
将队列改为优先队列Q使用上述关键字在图中的所有顶点
而Q不空
- 弹出顶点u与Q中
- 最低键对于每个相邻的顶点v u的做
  - 如果（v是仍然在Q）和（键（U）+权重函数（U，v）<键（v）），然后
    - 集合U为v的父
    - 更新v程序的键等于键（U）+权重函数（U，v）//这部分给我带来了问题，因为我不知道如何在优先级qu中实现reduceKey EUE

来源

2013-01-19 user1641700

我很高兴你接受你的答案，有没有任何理由，你没有upvote呢？ – imslavko

我只有5个声望，我需要15个upvote所以... – user1641700

我不认为你可以在STL容器实现它。请记住，您始终可以根据矢量编写自己的堆（优先队列），但有一项解决方法：

保留您拥有的距离数组，例如d。在你的优先级队列中你放置了这对距离和这个距离的顶点索引。当您需要从队列中删除一些值时，请不要删除它，只需更新d阵列中的值并将新队列放入队列。

每当您从队列中获取新值时，请检查pair中的距离是否确实如此，如在您的数组d中。如果没有忽略它。

时间是相同的O（MlogM）。内存是O（MlogM），其中M是边的数量。还有另外一种方法：使用RB-Tree，它可以插入和删除O（logN）中的键并获得最小值。您可以在std::set容器中的RB-Tree的STL中找到实现。但是，虽然时间复杂度相同，但RB-Tree的工作速度较慢，隐藏常数较大，所以它可能会稍微慢一点，appx。慢了5倍。当然，取决于数据。

来源

2013-01-19 09:13:45 imslavko

谢谢〜示例代码：http://pastie.org/9097197 – fizzbuzz

该解决方案不是最优的，因为你将有大量的虚拟数据在你的优先级队列。首先，你插入N个节点，然后你更新每个节点（在最坏的情况下），所以你最终会在你的队列中有2 * N个元素。如果N很大，推压操作会很慢，因为随着N变大，log N变大。我认为最好的解决方案是在队列中存储指向元素的指针。以这种方式，你更新一个元素，然后调用make_heap，它取N（常数）为O（log N）。 –

最初的问题是要求渐近快速的东西，只使用STL。这就是我的答案所提供的。 – imslavko

对于另一种方法：比使用std :: set更好。您可以使用btree :: btree_set（或btree :: safe_btree_set）。这是一个与谷歌使用B-Tree制作的std :: set相同的实现，与使用RB-Tree的stl不同。这比std :: set和O（logN）好得多。检查性能比较： http://code.google.com/p/cpp-btree/wiki/UsageInstructions 而且它也有更低的内存占用。

来源

2013-02-26 12:39:27 user1811468

好点。我的回答更像是“使用任何平衡的二叉搜索树” – imslavko

我不是专家，所以希望这不是太愚蠢，但将矢量结合lower_bound工作得很好吗？

如果您使用lower_bound找到插入新值的正确位置，您的矢量将始终在构建时进行排序，无需排序。当你的向量被排序时，是不是lower_bound具有对数类性能的二进制搜索？

因为它是排序的，所以找到最小值（或最大值）是一个快照。

要减少密钥，您需要再次执行lower_bound搜索，删除操作并再次执行lower_bound操作，以插入缩减密钥，即= 2对数类操作。还不错。

或者，您可以更新密钥并对向量排序。我会猜测随机访问，这应该仍然是在对数类，但不知道那里确实是什么。

使用排序向量，如果您知道候选关键字小于其中的关键字，那么也许您甚至可以对矢量中具有所有较小值的部分进行排序，以获得更好的性能。

另一个考虑是我认为sets/maps比vector有更多的内存开销吗？

来源

2015-02-06 16:42:24

我认为大多数排序仅限于NLogN，所以2个LogN用于重新插入而不是排序可能会更好地用于缩减关键操作。

另一件事是插入矢量并不是那么热，但总体来说，矢量w lower_bound的想法似乎值得考虑？

谢谢

来源

2015-02-06 20:42:33

在STL优先级队列中实现decreaseKey队列C++

回答

相关问题