Python heapq 替换优先级

Question

我正在尝试使用 Python 的 heapq 来实现 Dijkstra 的算法。如果发现通往它的较短路径，则该算法需要更改单元格的值。

我正在通过此检查执行此操作:

if curr_cell[0] + val < prev_cell[0]:  # value of new path is less than old value
    new_cell = (curr_cell[0] + val, prev_cell[1], curr_cell[1])
    heap[index] = new_cell
    heapify(heap)

但是，当在更大的迷宫上运行我的程序时，这需要很长时间，可能是因为 heapify()称呼。

更改堆入口优先级的更有效方法是什么？

Answer 1

heapq 库不支持有效地更新优先级，因为没有有效的方法来搜索堆。如果在 O(n) 时间内搜索堆并手动替换元素，则可以使用 _siftup() 和 _siftdown() 来恢复堆不变量。

或者，这是我编写的兼容实现，它使用 dict 来允许 O(1) 查找堆索引。

https://github.com/elplatt/python-priorityq