如何在Dijkstra算法中使用二进制堆？

Question

我正在编写dijkstra算法的代码，对于我们应该找到与当前使用的节点之间距离最小的节点的部分，我使用了一个数组，并完全遍历它来找出节点。

这部分可以用二进制堆代替，我们可以在O（1）时间内计算出节点，但是我们也在进一步的迭代中更新节点的距离，我将如何合并那个堆？

对于数组，我所要做的就是转到（ith-1）索引并更新该节点的值，但在二进制堆中不能做同样的事情，我必须进行完整的搜索以确定节点的位置，然后更新它。

这个问题的解决方法是什么？

Answer 1

除了Min-Heap数组之外，我还会使用哈希表来完成此操作。

哈希表具有被哈希编码为节点对象的键和值，这些值是这些节点在最小堆数组中的位置的索引。

然后，每当您在min-heap中移动一些东西时，您只需要相应地更新哈希表。由于在min-heap中每个操作最多移动2个元素（即它们被交换），并且我们每次移动的成本是O（1）来更新哈希表，那么我们就不会损坏min-heap操作的渐近边界。例如，minHeapify是O（lnn）。我们刚刚为每个minHeapify操作添加了2个O（1）哈希表操作。因此总体复杂度仍然是O（lgns）。

请记住，您需要修改在最小堆中移动节点的任何方法来执行此跟踪！例如，minHeapify（）需要使用Java进行如下修改：

Nodes[] nodes;
Map<Node, int> indexMap = new HashMap<>();

private minHeapify(Node[] nodes,int i) {
    int smallest;
    l = 2*i; // left child index
    r = 2*i + 1; // right child index
    if(l <= heapSize && nodes[l].getTime() < nodes[i].getTime()) {
        smallest = l;
    }
    else {
        smallest = i;
    }
    if(r <= heapSize && nodes[r].getTime() < nodes[smallest].getTime()) {
        smallest = r;
    }
    if(smallest != i) {
        temp = nodes[smallest];
        nodes[smallest] = nodes[i];
        nodes[i] = temp;
        indexMap.put(nodes[smallest],i); // Added index tracking in O(1)
        indexMap.put(nodes[i], smallest); // Added index tracking in O(1)
        minHeapify(nodes,smallest);
    }
}

BuildMinHeap，heapExect应该依赖于minHeapify，所以其中一个基本上是固定的，但是您确实需要从哈希表中删除提取的密钥。您还需要修改decreseKey来跟踪这些更改。一旦修复，那么插入也应该被修复，因为它应该使用decreseKey方法。这应该涵盖了所有的基础，并且您不会改变算法的渐近边界，并且您仍然可以继续使用堆作为优先级队列。

请注意，在这个实现中，斐波那契最小堆实际上比标准最小堆更受欢迎，但这是完全不同的蠕虫。

Answer 2

我在使用任何形式的堆时遇到的问题是，您需要重新排序堆中的节点。为了做到这一点，您必须不断从堆中弹出所有内容，直到找到所需的节点，然后更改权重，并将其推回（以及弹出的其他内容）。老实说，仅仅使用数组可能会更高效，更容易编码。

我解决这个问题的方法是使用一棵红黑树（在C语言中，它只是集合）

除了树，我还保留了一个包含给定节点距离的双精度数组。因此，当我需要对树中的一个节点重新排序时，我只需使用与dist数组之间的旧距离以及节点名，就可以在集合中找到它。然后，我将从树中删除该元素，并以新的距离将其重新插入树中。搜索节点O（logn）并插入节点O（logn），因此重新排序节点的成本是O（2*logn）=O（logn）。对于二进制堆，它还有一个用于插入和删除的O（logn）（不支持搜索）。因此，删除所有节点直到找到所需节点的代价是，更改其权重，然后将所有节点重新插入。一旦节点被重新排序，我就会改变数组中的距离以反映新的距离。

老实说，我想不出一种方法来修改堆，使其能够动态更改节点的权重，因为堆的整个结构都基于节点保持的权重。

Answer 3

这只是我在课堂上做这件事时发现的一些信息，我和我的同学分享了。我想我会让人们更容易找到它，我把这篇文章留了下来，这样当我找到解决方案时就可以回答它。

注意：在这个例子中，我假设图形的顶点有一个ID来跟踪哪个是哪个。这可能是一个名称、一个数字，不管什么，只要确保在下面的struct中更改类型即可。如果没有这样的区分方法，那么可以使用指向顶点的指针，并将其指向的地址进行比较

你在这里面临的问题是，在Dijkstra的算法中，我们被要求将图的顶点和它们的键存储在这个优先级队列中，然后更新队列中剩下的键。但是...堆数据结构无法到达不是最小节点或最后节点的任何特定节点！
我们能做的最好的事情就是在O（n）时间内遍历堆找到它，然后更新它的密钥并在O（Logn）处冒泡。这使得更新每个边的所有顶点O（n），使得我们对Dijkstra O（mn）的实现比最佳O（mLogn）差得多。

Bleh！一定有更好的方法！

因此，我们需要实现的并不是一个标准的基于最小堆的优先级队列。我们需要一个比标准4 pq操作更多的操作：

1. IsEmpty

为了DecreseKey，我们需要：

• 在堆中查找特定顶点

本质上，由于您（我假设它在过去4个月的某个时候已经实现）可能会使用“基于数组”的堆实现，这意味着我们需要堆来跟踪数组中的每个顶点及其索引，以使此操作成为可能。

设计一个结构比如：（c）

struct VertLocInHeap
{
    int vertex_id;
    int index_in_heap;
};

将允许您跟踪它，但是将它们存储在数组中仍然会给您O（n）时间来查找堆中的顶点。没有复杂性改进，而且比以前更复杂。

1. 将此信息存储在二进制搜索树中，其键值为“顶点id”

我实际上使用了一个std:：map声明为：std:：map m_locations；在堆中，而不是使用结构。第一个参数（键）是顶点id，第二个参数（值）是堆数组中的索引。因为std:：map保证了O（Logn）搜索，所以它可以很好地开箱即用。然后，无论何时插入或冒泡，只要m_locations[vertexID]=newLocationInHeap
轻松赚钱。

分析：
优势：我们现在有O（Logn）来寻找p-q中的任何给定顶点。对于冒泡，我们做O（Log（n））移动，对于每个交换，在数组索引映射中做O（Log（n））搜索，导致冒泡的O（Log^2（n）操作。
所以，我们有一个日志（n）日志^2（n）=O（Log^2（n））用于更新堆中单个边的键值的操作。这使得我们的Dijkstra alg取O（mLog^2（n））。这非常接近理论上的最佳，至少是我能得到的最接近的。真棒负鼠！
缺点：我们在内存中为堆存储的信息实际上是原来的两倍。是不是“现代”的问题？不完全是；我的桌面可以存储80亿整数，许多现代电脑至少有8GB的内存；然而，这仍然是一个因素。如果您使用40亿顶点图来实现这个实现，这可能比您想象的要频繁得多，那么它会导致一个问题。此外，所有这些额外的读写可能不会影响分析的复杂性，但在某些机器上可能仍然需要时间，特别是如果信息存储在外部。

我希望这对将来的人有所帮助，因为我花了很长时间找到了所有这些信息，然后把我从这里、那里和任何地方得到的信息拼凑在一起形成了这个。我责怪互联网和睡眠不足。