优先级队列如何与堆一起使用来解决最小距离问题

Question

请原谅我，我对数据结构非常陌生。

我很困惑，如何使用一个priroity队列来解决最小距离。例如，如果我有一个矩阵，想找到从源点到目的地的最小距离，我知道我会执行Dijkstra算法，其中有一个队列，我可以很容易地找到源点和矩阵中所有元素之间的距离。

然而，我很困惑，这里如何使用堆+优先级队列。比如说，我从 (1,1) 的最小距离，并想知道到 (3,3) 我知道如何实现寻找邻居和检查距离并标记为访问的算法。但是我读到了优先级队列和最小堆，想实现这些。

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

总而言之，我不明白min堆+优先级队列是如何用寻找距离这种东西的min的。

    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

如果我对你的问题理解正确的话，你在这一点上被卡住了。

但是用pq的话，堆在这里怎么能有两个以上的邻域呢？例如(1,1)的子代就是上面说的4个邻居。这就违背了2*i和2*i+1以及i2

听起来好像是什么绊住了你的脚步，是有两个独立的概念，你可能把它们结合在一起了。首先，有一个概念是 "一个网格中的两个地方可能是彼此相邻的"。在那个世界里，你的每个位置有（最多）四个邻居。其次，是二进制堆的形状，其中每个节点都有两个子节点，它们的位置由数组索引上的某些算术计算给出。这些完全是相互独立的--二进制堆不知道它存储的项目来自一个网格，而网格也不知道有一个数组，每个节点有两个子节点存储在特定的位置。

例如，假设你想在二进制堆中存储位置(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

这棵树仍然给每个节点两个子节点，只是这些子节点不一定会映射回网格中节点的相对位置。

更一般地说，把优先级队列当作一个黑盒子。想象一下，它只是一个神奇的设备，它说 "你可以给我一些新的东西来存储"，"我可以给你最便宜的东西，你给的是目前为止"，仅此而已。事实上，在内部，它恰好是以二进制堆的形式实现的，这基本上是无关紧要的。

希望对大家有所帮助!