构建基于迭代器的提升优先级队列

Question

我有一个binomial_heaps的列表，并且我必须更新某些binomial_heaps中某个元素的优先级。为此，我使用boost binomial_heap的更新功能。然而，我必须彻底移除和重建一个binomial_heaps（因为所有优先级都会改变）。而不是每次都使用推送（如果我理解正确的话会有n * log（n）的复杂性），我想根据底层容器的迭代器构造它（一种heapify或make_heap操作，它会是线性时间）。这在标准priority_queue中似乎是可能的，但不在升压实施中。另一方面，标准的不提供更新功能。有没有办法解决这个问题，我可以同时支持这两种方法，或者支持两者的另一个库。或者，也许我的推理，推动一个空优先级队列上的所有元素较慢，是不正确的？

有些人可能会说，我需要重建一个完整的优先级队列，这将使优先级队列的使用变得完全多余，这是一个严重问题。我想实现的算法是“在Aaron Clauset的超大型网络中查找社区结构”，其中作者正是这样做的（除非我没有正确解释它）

（对不起，不能发布链接到因为我没有足够的声望来发布超过2个链接）

Answer 1

Clauset等人的“快速模块性”算法。 （paper here,code here）使用一对链接的数据结构。一方面，你有一个稀疏矩阵数据结构（它实际上只是一个邻接列表，它不是将一个特定数组元素作为链表来存储，而是使用平衡二叉树数据结构来存储它们），和一个最大堆。稀疏矩阵中的所有值（其实是算法中潜在合并的dQ_ij值）也存储在最大堆中。

所以，最大堆只是找到最具正值的稀疏矩阵中的边的一种有效方法。一旦你有那边的ij对，你想要将列（行）i的元素“插入”列（行）j的元素中，然后你想删除列（行）i。所以，你不会在每次从最大堆流出后重建整个max-heap。相反，您希望从中删除一些元素（从稀疏矩阵中删除的行/列中的元素），并更新其他元素的值（更新后的行/列中的值为j）。

这是链接的数据结构有用的地方 - 在原始实现中，稀疏矩阵中的每个元素都存储一个指向max-heap中相应条目的指针，以便如果更新稀疏矩阵中的值，你可以在max-heap中找到相应的元素并更新它的值。一旦你这样做，你需要重新heapify更新的堆元素，让它在堆中上下移动（递归）。同样，如果删除稀疏矩阵中的元素，则可以在堆中找到它的条目并在其上调用删除函数。