时间戳

首页 > 解决方案 > 优先级队列如何与堆一起使用来解决最小距离

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

问题描述

请耐心等待我对数据结构很陌生。

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

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

现在，我唯一的理解是优先级队列有一个定位元素的键。我的问题是当我插入第一个邻居(1,0),(0,0),(2,1),(1,2)时，它们基于一个键（在这种情况下是距离）插入到 pq 中。因此，下一个搜索将是矩阵中距离最短的元素。但是对于 pq，如何在这里使用超过 2 个邻居的堆？例如，孩子(1,1)是上述 4 个邻居。这将违背2*iand2*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|

标签： javaalgorithmheappriority-queuedijkstra

解决方案

您需要使用优先级队列来获得每次移动的最小权重，因此 MinPQ 将适合此。

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

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

推荐阅读