是否有可能使用堆实现最小优先级队列，还是需要二进制堆？

Question

对于我的任务，我一直在研究satnav系统，并使用邻接列表来存储所有的映射数据。

我希望为我的路径规划功能实现dijkstras算法，但我需要首先实现最小优先级队列。是可以使用常规堆做到这一点，或者是需要二进制的？

Answer 1

看起来你的意思是regular heap作为用于动态内存分配的内存区域。此术语与术语heap无关，因为数据结构（二进制堆特殊情况）表示一组值，以特定方式排序

Answer 2

您可以实现具有常规（基于数组的）基于最小优先级的队列）堆很容易，但Dijkstra的算法需要支持额外的操作：您必须能够找到任何给定的项目并动态降低其优先级。

基于数组的堆通常不会找到除根之外的任何项的有效方法，因此您需要添加一种方法来实现此目的。

一个简单的方法是维护包含堆数组中每个项目索引的第二个数组（如果该项不在堆中，则为-1）。无论何时添加，删除或交换堆项，都必须更新此数组。