相关疑难解决方法(0)

我正在开发一个演示Djikstra算法的应用程序,并且要使用它,我需要在我的元素值减少时恢复堆属性.

关于复杂的问题是,当算法改变的元素的值,该元素的索引用于优先级队列中的内部结构(堆在这种情况下)是未知的.因此,我之前需要进行O(n)搜索,以便恢复索引,然后才能对其执行实际的减少键.

而且,我不确定操作所需的实际代码.我在这里使用D-Heap 作为我的优先级队列.伪代码会有所帮助,但我更喜欢Java中的一个例子,说明应该如何做.

我知道有可能在O(log n)中实现减少键功能,但我不知道怎么做？

使用最小/最大堆算法时,优先级可能会发生变化.处理此问题的一种方法是删除并插入元素以更新队列顺序.

对于使用数组实现的优先级队列,这可能是一个似乎可以避免的性能瓶颈,特别是对于优先级变化较小的情况.

即使这不是优先级队列的标准操作,这也是一个可以根据我的需要进行修改的自定义实现.

是否有众所周知的最佳实践方法来更新min/max-heap中的元素？

背景信息:我不是二叉树专家,我继承了一些代码,这些代码在优先级队列中重新插入了元素.我为重新排序新元素的min-heap做了一个重新插入函数 - 这给了一个可测量的改进(删除和插入),但这似乎是其他人可能已经解决的更优雅的问题办法.

我可以链接到代码,如果它有所帮助,但宁愿不太关注实现细节 - 因为这个Q&A可能保持一般.

我想了解这些容器在时间复杂度方面的主要区别。我尝试了 Dijkstra 算法的 3 种实现，如下所述：

1-使用一个简单的数组作为队列

2-使用STLpriority_queue

3-带有STL集

我测试过的图相当大，它包含超过 150000 个顶点，有方向且所有边的权重均为正。

我得到的结果如下：

1 - 使用数组时，算法相当慢 --> 这是预期的

2 - 使用 STLpriority_queue 算法运行速度比数组快很多 --> 这也是预期的

3 - 使用STL设置，算法运行得非常快，我说的是比priority_queue快100倍 --> 我没想到会看到如此巨大的性能......

知道 std::priority_queue 和 std::set 是存储元素的数据容器，并且两者都具有基本相同的插入复杂度 O(log n)，我不明白它们之间的性能差异如此之大。对此你有什么解释吗？

感谢您的帮助，

编辑： 这是我的实现的摘要：

与 std::set:

unsigned int Graphe::dijkstra(size_t p_source, size_t p_destination) const {

....


set<pair<int, size_t>> set_vertices;


vector<unsigned int> distance(listAdj.size(),
        numeric_limits<unsigned int>::max());


vector < size_t
        > predecessor(listAdj.size(),
                numeric_limits < size_t > ::max());


distance[p_source] = 0;
set_vertices.insert( { 0, p_source });


while (!set_vertices.empty()) {

    unsigned …

在大多数伪代码中,我通常会发现以下内容:

• DeleteMin(返回具有最小键的元素并将其从集合中删除.)

• DecreaseKey(适应特定元素键值的减少)

• 为什么使用DeleteMin来检索最小元素 - 为什么不是随机元素？
• DecreaseKey的目的是什么？在伪代码中,它总是在元素的值改变之后调用.它在做什么？