是否有可能使用堆實現最小優先級隊列，還是需要二進制堆？

Question

對於我的任務，我一直在研究satnav系統，並使用鄰接列表來存儲所有的映射數據。

我希望爲我的路徑規劃功能實現dijkstras算法，但我需要首先實現最小優先級隊列。是可以使用常規堆做到這一點，或者是需要二進制的？

Answer 1

看起來你的意思是regular heap作爲用於動態內存分配的內存區域。此術語與術語heap無關，因爲數據結構（二進制堆特殊情況）表示一組值，以特定方式排序

Answer 2

您可以實現具有常規（基於數組的）基於最小優先級的隊列）堆很容易，但Dijkstra的算法需要支持額外的操作：您必須能夠找到任何給定的項目並動態降低其優先級。

基於數組的堆通常不會找到除根之外的任何項的有效方法，因此您需要添加一種方法來實現此目的。

一個簡單的方法是維護包含堆數組中每個項目索引的第二個數組（如果該項不在堆中，則爲-1）。無論何時添加，刪除或交換堆項，都必須更新此數組。