优先级队列如何与堆一起用于求解最小距离
请容忍我，我对数据结构非常陌生。
我对如何使用优先级队列来求解最小距离感到困惑。例如，如果我有一个矩阵，想要找到从源到目标的最小距离，我知道我将执行Dijkstra算法，在该算法中，通过队列，我可以轻松找到源和矩阵中所有元素之间的距离。
然而，我对这里如何使用堆优先级队列感到困惑。例如，假设我从网格上的（1,1）开始，并希望找到到（3,3）的最小距离，我知道如何实现该算法，即查找邻居、检查距离和标记访问。但我读过关于优先级队列和最小堆的文章，我想实现它。
现在，我唯一的理解是优先级队列具有定位元素的键。我的问题是，当我插入第一个邻居（1,0），（0,0），（2,1），（1,2）时，它们会根据键（在这种情况下是距离）插入pq。因此，下一次搜索将是矩阵中距离最短的元素。但是有了pq，一个堆怎么能在这里与两个以上的邻居一起使用呢？例如，（1,1）的子代是上述4个邻居。这将违反2*i和2*i1和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|
共有2个答案
如果我正确理解了你的问题，你就陷入了困境：
但是有了pq，一个堆怎么能在这里与两个以上的邻居一起使用呢？例如，（1,1）的孩子是上述4个邻居。这将与2*i和2*i 1和i/2相反
听起来让你困惑的是，这里有两个不同的概念，你可能会结合在一起。首先，有“网格中的两个位置可能相邻”的概念在这个世界上，每个位置最多有四个邻居。接下来是二进制堆的形状，其中每个节点有两个子节点，其位置由数组索引上的某些算术计算给出。这些是完全独立的——二进制堆不知道它存储的项来自网格，网格也不知道每个节点有两个子节点存储在特定位置的数组。
例如，假设要在二进制堆中存储位置（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
这个树仍然给每个节点两个子节点；这些子节点不一定映射回网格中节点的相对位置。
更一般地说，将优先级队列视为黑盒。想象一下，它只是一个神奇的装置，上面写着“你可以给我一些新的东西来储存”和“我可以给你迄今为止最便宜的东西”，就这样。在内部，它碰巧被实现为一个二进制堆，这一事实在本质上是不相关的。
希望这能有所帮助！
-
我目前正在尝试实现min heap PQ，但是我在实现的正确性方面遇到了一些问题，我似乎无法找出我做错了什么——它没有输出最低优先级，也没有对它们进行正确排序。 使用以下测试数据： 我得到以下结果： 我希望结果是按升序排列的——起初我认为这可能是因为交换了错误的孩子，但最后一个输出是最大的优先级，所以这没有意义。我花了几个小时试图研究堆优先级队列，但我找不到任何帮助。 以下是CMP要求的更好的代码
-
我一直在努力实现Dijkstra的算法；更具体地，具有优先级队列的部分。将顶点添加到数据结构中，并使用迭代器遍历所有顶点并找到最小距离；这很容易，但这次是。 我想要的是： < li >能够将顶点插入数据结构中 < li >提取(返回并移除)距离dist[v]最小的顶点v 我相信为了让Dijkstra的算法正常工作，你应该能够在恒定时间内插入顶点并在log（n）时间内提取它们；有人建议可以使用优先级
-
注意：我知道可以用比较器创建优先级队列，然后重复调用Add。
-
我在CLRS，第三版（第662页）中读到了Dijkstra的算法。下面是我不明白的书中的一部分： 如果图足够稀疏--特别是-我们可以通过用二进制最小堆实现最小优先级队列来改进算法。 为什么图形应该是稀疏的？ 下面是另一部分：
-
我正在编写一个涉及堆实现的代码，在我的bubbleUp方法中，在我的while循环行中，我似乎遇到了一个取消引用的错误。这可能是一个相当基本的问题，但解决这个问题的最佳方法是什么？我在实现removeHigh方法时也遇到了一些问题，该方法旨在从队列中移除最高的元素。
-
我的问题是：每个节点的优先级是什么？我认为它是最小值的传入边缘的权重，但我不确定。这是真的吗？ 第二个问题，当我提取队列的根时，如果这个节点不与任何一个被访问的节点邻接，它将如何工作？