構建基於迭代器的提升優先級隊列

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更新的堆元素，讓它在堆中上下移動（遞歸）。同樣，如果刪除稀疏矩陣中的元素，則可以在堆中找到它的條目並在其上調用刪除函數。