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

Question

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

Dijkstra 算法实现的性能

实现 Dijkstra 算法

鉴于 STL 不包含用于更新键的堆函数，对堆中的顶点重新排序（第 19 行）的最佳方法是什么？

Answer 1

您需要让顶点在堆中“冒泡”（根据需要将其与其父级交换），直到它到达堆中的新位置。

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

Answer 2

我想有几种方法可以做到这一点。

您可以手动进行筛选操作，基本上将值带到堆的顶部，弹出它，然后用它的新值将它推回堆上。

您可以更新该值并在堆上再次执行 make_heap，假设 make_heap 设计为在堆已经“几乎是堆”时高效。

您可以用一些标志标记堆中的节点以指示它不再有效，然后将具有新值的新元素推送到堆上。然后，每次从堆中弹出一个元素时，都会检查标志的有效性并忽略任何无效元素。

否则，您可以使用另一个具有更新功能的堆实现。例如，Boost.Graph 库在其详细信息（boost/graph/detail 文件夹）中包含一个 d_ary_heap.hpp 标头，该标头实现了一个 D-Ary 堆间接实现，该实现确实具有一个更新函数是 logN。这在 Dijkstra 和 A* 的 BGL 实现中使用，您也可以直接使用它而不是自己实现。