使用STL make_heap实现Dijkstra算法

Question

至少有几个答案建议使用STL堆函数在Dijkstra算法中实现优先级队列:

Dijkstra算法实现的性能

实现Dijkstra算法

考虑到STL不包含用于更新密钥的堆函数,在堆中重新排序顶点(第19行)的最佳方法是什么？

Answer 1

你需要让顶点'冒泡'通过堆(根据需要与其父进行交换),直到它到达堆中的新位置.

在伪c ++改编自Introduction to Algorithms 2nd ed.皮克.140:

heap[pos] = new_weight;
while (pos > 0 && heap[parent(pos)] > heap[pos]) {
    swap(heap[parent(pos)], heap[pos]);
    pos = parent(pos);
}

哪里 int parent(int pos) { return (pos-1)/2; }