在C ++中使用密钥更新使用最小优先级队列的最简单的方法

有时候在编程竞赛等时候，我们需要一个简单的最小优先级队列的实现，用reduce-key来实现Dijkstraalgorithm等等。我经常使用set <pair <key_value，ID>和一个数组（映射ID – > key_value ）一起来实现这一点。

• 将元素添加到集合需要O（log（N））时间。 要从N个元素中构build优先级队列，我们​​只需将它们逐个添加到集合中。 这总共需要O（N log（N））时间。

• 具有min key_value的元素只是该集合的第一个元素。 探测最小的元素需要O（1）次。 删除它需要O（log（N））时间。

• 为了testing一些ID = k是否在集合中，我们首先在数组中查找它的key_value = v_k，然后search集合中的元素（v_k，k）。 这需要O（log（N））时间。

• 为了将一些ID = k的key_value从v_k改为v_k'，我们首先在数组中查找它的key_value = v_k，然后search该集合中的元素（v_k，k）。 接下来，我们从集合中删除该元素，然后将元素（v_k'，k）插入集合中。 然后，我们也更新数组。 这需要O（log（N））时间。

虽然上述方法可行，但大多数教科书通常build议使用二进制堆实现优先级队列，因为构build二进制堆的时间只是O（N）。 我听说在C ++的STL中有一个使用二进制堆的内置优先级队列数据结构。 但是，我不知道如何更新该数据结构的key_value。

在C ++中使用密钥更新来使用最小优先级队列的最简单和最有效的方法是什么？

Answer 1

那么，正如Darren所说的那样， std::priority_queue没有减less元素优先级的方法，也没有删除当前最小值的元素。 但默认的std::priority_queue只不过是一个std::vector的简单容器适配器，它使用<algorithm> （ std::push_heap ， std::pop_heap和std::make_heap ）的std堆函数。 所以对于Dijkstra（你需要优先更新），我通常只是自己做这个，并使用一个简单的std::vector 。

一个推动就是O（log N）操作

 vec.push_back(item); std::push_heap(vec.begin(), vec.end()); 

当然，对于从N个元素重新构build一个队列，我们​​并不是使用这个O（log N）操作（使得整个事物O（Nlog N））来推动它们，而是将它们全部放入向量中，接着是简单的O （N）

 std::make_heap(vec.begin(), vec.end()); 

min元素是一个简单的O（1）

 vec.front(); 

pop是简单的O（log N）序列

 std::pop_heap(vec.begin(), vec.end()); vec.pop_back(); 

到目前为止，这只是std::priority_queue通常在底层做的事情。 现在要改变一个项目的优先级，我们只需要改变它（然而它可能被合并到项目的types中）并且使序列再次成为一个有效的堆

 std::make_heap(vec.begin(), vec.end()); 

我知道这是一个O（N）操作，但是另一方面，这消除了使用额外的数据结构跟踪项目在堆中的位置的任何需要，或者（更糟糕的是）增加了项目的types。 考虑到易用性， std::vector （也会影响运行时）的紧凑和线性内存使用率，以及我经常使用graphics的事实，对数优先级更新的性能损失实际上不是那么重要无论如何，都有相当less的边（在顶点数上是线性的）。

在所有情况下，这可能不是最快的方法，但肯定是最简单的。

编辑：哦，因为标准库使用最大堆，你需要使用等价于比较优先级（但是你从项目中获得），而不是默认的<运营商。

Answer 2

我不认为std::priority_queue类允许有效实现decrease-key风格的操作。

我推出了自己的基于二进制堆的数据结构，支持这一点，基本上沿着非常相似的线，你已经描述了基于std::set的优先级队列：

• 维护一个二进制堆，按照存储pair<value, ID>元素的pair<value, ID>和映射ID -> heap_index的数组进行ID -> heap_index 。 在heapify_up, heapify_down等堆例程中heapify_up, heapify_down必须确保映射数组与当前元素的堆位置保持同步。 这增加了一些额外的O(1)开销。
• 根据这里描述的标准algorithm，可以在O(N)完成数组到堆的转换。
• 在根元素上偷看是O(1) 。
• 检查一个ID是否当前在堆中只需要在映射数组中进行O(1)查找。 这也允许O(1)在与任何ID相对应的元素上偷看。
• Decrease-key需要在映射数组中进行O(1)查找，然后通过heapify_up, heapify_down对O(log(N))更新。
• 把一个新的项目放在堆上是O(log(N))就像从堆中popup一个正在退出的项目一样。

所以渐近地说，与基于std::set的数据结构相比，一些操作的运行时间得到了改进。 另一个重要的改进是二进制堆可以在数组上实现，而二叉树则是基于节点的容器。 二进制堆的额外数据位置通常转化为改进的运行时间。

这个实现的一些问题是：

• 它只允许整数项目ID 。
• 它假定物品ID的分布紧密，从零开始（否则映射arrays的空间复杂度就会爆炸！）。

如果您维护一个映射哈希表，而不是映射数组，但是运行时间稍微多一点，则可能会克服这些问题。 对我来说，整数ID总是够用的。

希望这可以帮助。

Answer 3

尽pipe我的回答不会回答原来的问题，但是我认为在尝试在C ++ / Java中实现Dijkstraalgorithm（如我自己）时，遇到这个问题的人可能会很有用，

如前所述，C ++中的priority_queue （或Java中的PriorityQueue ）不提供decrease-key操作。 在实现Dijkstra时使用这些类的一个很好的技巧是使用“懒惰删除”。 Dijkstraalgorithm的主循环从优先级队列中提取下一个要处理的节点，并分析其所有相邻节点，最终改变优先级队列中节点的最小path代价。 这是通常需要decrease-key才能更新该节点的值的地方。

诀窍是根本不改变它 。 相反，该节点的“新副本”（以其新的更好的成本）被添加到优先级队列中。 成本较低的情况下，该节点的新副本将在队列中的原始副本之前被提取，因此将被更早地处理。

这种“懒惰删除”的问题是，具有较高的不利代价的节点的第二副本将最终从优先级队列中提取出来。 但是，在第二次添加副本之后总会发生这种情况，成本更高，正在处理中。 所以，当从优先级队列中提取下一个节点时，主要的Dijkstra循环必须做的第一件事是检查节点是否先前被访问（并且我们知道最短path已经）。 正是在这个时刻，我们将要进行“懒惰的删除”，并且元素必须被忽略。

这个解决scheme在内存和时间上都会有成本，因为优先级队列正在存储我们还没有移除的“死元素”。 但真正的成本将是相当小的，编程这个解决scheme，恕我直言，比任何其他尝试模拟丢失decrease-key操作的替代scheme更容易。