c++ - 使用 STL make_heap 实现 Dijkstra 算法

Question

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

Performance of Dijkstra's algorithm implementation

Implementing Dijkstra's Algorithm

鉴于 STL 不包含用于更新键的堆函数，在堆 (line 19) 中重新排序顶点的最佳方法是什么？

Answer 1

您需要让顶点在堆中“向上冒泡”(根据需要与父节点交换)，直到它到达堆中的新位置。

在改编自《算法导论》第 2 版的伪 C++ 中。页。 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; }