可以用堆实现最小优先级队列，还是需要二进制堆？
在我的任务中，我一直在研究一个卫星导航系统，我使用邻接列表来存储所有的地图数据。
因此，我想为我的路径规划函数实现dijkstras算法，但我需要首先实现一个最小优先级队列。使用常规堆可以做到这一点吗，还是需要二进制堆？
共有2个答案
您可以很容易地使用常规（基于数组的）堆实现最小优先级队列，但Dijkstra的算法需要支持额外的操作：您必须能够找到任何给定项并动态降低其优先级。
基于数组的堆通常不会提供有效的方法来查找除根之外的任何项，因此需要添加一种方法。
一种简单的方法是维护一个第二个数组，其中包含堆数组中每个项目的索引（如果项目不在堆中，则为 -1）。每当添加、删除或交换堆项目时，都必须更新此数组。
你的意思似乎是< code >常规堆作为用于动态内存分配的内存区域。该术语与术语< code >堆没有关系，因为数据结构(二进制堆是一种特殊情况)表示一组以特定方式排序的值
-
我目前正在尝试实现min heap PQ，但是我在实现的正确性方面遇到了一些问题，我似乎无法找出我做错了什么——它没有输出最低优先级，也没有对它们进行正确排序。 使用以下测试数据： 我得到以下结果： 我希望结果是按升序排列的——起初我认为这可能是因为交换了错误的孩子，但最后一个输出是最大的优先级，所以这没有意义。我花了几个小时试图研究堆优先级队列，但我找不到任何帮助。 以下是CMP要求的更好的代码
-
我不熟悉堆，二进制堆，我试图理解为什么我们需要使用二进制堆实现优先级队列。我还了解到二进制堆的底层数据结构也是一个数组。 所以我的问题是，为什么我们不能使用一个数组，按降序（对于最大堆）或升序（对于最小堆）排序来表示优先级队列？这里我可能错了，但我认为，如果以这种方式实现，findMax、findMin、insert和delete等操作的时间复杂度将几乎保持不变。那么，我们是否可以不使用排序数组来
-
我正在编写一个涉及堆实现的代码，在我的bubbleUp方法中，在我的while循环行中，我似乎遇到了一个取消引用的错误。这可能是一个相当基本的问题，但解决这个问题的最佳方法是什么？我在实现removeHigh方法时也遇到了一些问题，该方法旨在从队列中移除最高的元素。
-
问题内容： 总体而言，我正在尝试使用优先级队列来实现Dijkstra的算法。 根据golang-nuts的成员所述，Go中惯用的方法是将堆接口与自定义的基础数据结构一起使用。所以我像这样创建了Node.go和PQueue.go： 和PQueue.go： 和main.go ：（动作在SolveMatrix中） 问题是，在编译时我收到错误消息： 注释掉PQ.Push（firstNode）行确实使编译器
-
注意：我知道可以用比较器创建优先级队列，然后重复调用Add。
-
我在CLRS，第三版（第662页）中读到了Dijkstra的算法。下面是我不明白的书中的一部分： 如果图足够稀疏--特别是-我们可以通过用二进制最小堆实现最小优先级队列来改进算法。 为什么图形应该是稀疏的？ 下面是另一部分：