优先队列如何结合堆来解决min distance

Question

请耐心等待我是数据结构的新手。

我对如何使用优先级队列来解决最小距离感到困惑。例如，如果我有一个矩阵并想找到从源到目的地的最小距离，我知道我会执行 Dijkstra 算法，在该算法中，我可以使用队列轻松找到源与矩阵中所有元素之间的距离。

但是，我很困惑这里是如何使用堆+优先级队列的。例如，我从网格上的 (1,1) 开始，想找到到 (3,3) 的最小距离我知道如何在寻找邻居、检查距离和标记为已访问的意义上实现该算法.但是我已经阅读了有关优先级队列和最小堆的内容，并且想实现它。

现在，我唯一的理解是优先级队列有一个定位元素的键。我的问题是当我插入第一个邻居 (1,0),(0,0),(2,1),(1,2) 时，它们是根据键（在这种情况下是距离）插入到 pq 中的。那么接下来的搜索将是矩阵中距离最短的元素。但是有了 pq，堆怎么能在这里与超过 2 个邻居一起使用呢？例如 (1,1) 的 children 就是上面提到的 4 个邻居。这将违背 2*i 和 2*i + 1 和 i/2

总而言之，我不明白最小堆 + 优先级队列如何找到距离之类的最小值。

    0 1 2 3
     _ _ _ _
0 - |2|1|3|2|
1 - |1|3|5|1|
2 - |5|2|1|4|
3 - |2|4|2|1|

Answer 1

您需要使用优先级队列在每一步中获得最小权重，以便 MinPQ 适合这种情况。

MinPQ内部使用堆技术将元素放在正确的位置操作，例如sink() swim()

所以MinPQ是内部使用堆技术的数据结构

Answer 2

如果我正确地解释了你的问题，你就卡在了这里：

But with the pq, how can a heap be used here with more then 2 neighbours? For example the children of (1,1) are the 4 neighbours stated above. This would go against the 2*i and 2*i + 1 and i/2

听起来让您感到困惑的是这里有两个独立的概念，您可能将它们组合在一起。首先，有 "two places in a grid might be next to one another." 的概念在那个世界中，每个位置有（最多）四个邻居。接下来是二叉堆的形状，其中每个节点有两个 children ，其位置由数组索引的某些算术计算给出。它们完全相互独立——二叉堆不知道它存储的项目来自网格，而网格不知道有一个数组，其中每个节点有两个 children 存储在特定位置。

例如，假设您要在二叉堆中存储位置 (0, 0)、(2, 0)、(-2, 0) 和 (0, 2)，并且这些位置的权重分别为 1、2、3 和 4。那么二叉堆的形状可能是这样的：

               (0, 0)
              Weight 1
             /        \
          (2, 0)      (0, 2)
         Weight 2    Weight 4
           /
        (0, -2)
       Weight 3

这棵树还是给每个节点两个children；那些 children 不一定映射回网格中节点的相对位置。

更一般地说，将优先级队列视为一个黑盒子。想象一下，它只是一个显示 "you can give me some new thing to store" 和 "I can give you the cheapest thing you've given be so far" 的魔法装置，仅此而已。事实上，在内部，它恰好被实现为二进制堆，这一事实本质上是无关紧要的。

希望对您有所帮助！

优先队列如何结合堆来解决min distance

How priority queue is used with heap to solve min distance

java

algorithm

heap

dijkstra

priority-queue