我試圖實現Prim的算法，並且我需要爲優先級隊列（更新優先級隊列中的鍵值）使用decreaseKey方法。我可以在STL優先級隊列中實現嗎？在STL優先級隊列中實現decreaseKey隊列C++
如果有幫助，這是我下面的算法：每個頂點u在圖G的U至INFINITY
我不認爲你可以在STL容器實現它。請記住，您始終可以根據矢量編寫自己的堆（優先隊列），但有一項解決方法：
保留您擁有的距離數組，例如d。在你的優先級隊列中你放置了這對距離和這個距離的頂點索引。當您需要從隊列中刪除一些值時，請不要刪除它，只需更新d陣列中的值並將新隊列放入隊列。
每當您從隊列中獲取新值時，請檢查pair中的距離是否確實如此，如在您的數組d中。如果沒有忽略它。
時間是相同的O（MlogM）。內存是O（MlogM），其中M是邊的數量。還有另外一種方法：使用RB-Tree，它可以插入和刪除O（logN）中的鍵並獲得最小值。您可以在std::set容器中的RB-Tree的STL中找到實現。但是，雖然時間複雜度相同，但RB-Tree的工作速度較慢，隱藏常數較大，所以它可能會稍微慢一點，appx。慢了5倍。當然，取決於數據。
對於另一種方法：比使用std :: set更好。 您可以使用btree :: btree_set（或btree :: safe_btree_set）。 這是一個與谷歌使用B-Tree製作的std :: set相同的實現，與使用RB-Tree的stl不同。這比std :: set和O（logN）好得多。 檢查性能比較： http://code.google.com/p/cpp-btree/wiki/UsageInstructions 而且它也有更低的內存佔用。
好點。我的回答更像是「使用任何平衡的二叉搜索樹」 – imslavko
我不是專家，所以希望這不是太愚蠢，但將矢量結合lower_bound工作得很好嗎？
如果您使用lower_bound找到插入新值的正確位置，您的矢量將始終在構建時進行排序，無需排序。當你的向量被排序時，是不是lower_bound具有對數類性能的二進制搜索？
因爲它是排序的，所以找到最小值（或最大值）是一個快照。
要減少密鑰，您需要再次執行lower_bound搜索，刪除操作並再次執行lower_bound操作，以插入縮減密鑰，即= 2對數類操作。還不錯。
或者，您可以更新密鑰並對向量排序。我會猜測隨機訪問，這應該仍然是在對數類，但不知道那裏確實是什麼。
使用排序向量，如果您知道候選關鍵字小於其中的關鍵字，那麼也許您甚至可以對矢量中具有所有較小值的部分進行排序，以獲得更好的性能。
另一個考慮是我認爲sets/maps比vector有更多的內存開銷嗎？
我認爲大多數排序僅限於NLogN，所以2個LogN用於重新插入而不是排序可能會更好地用於縮減關鍵操作。
另一件事是插入矢量並不是那麼熱，但總體來說，矢量w lower_bound的想法似乎值得考慮？
謝謝
我很高興你接受你的答案，有沒有任何理由，你沒有upvote呢？ – imslavko
我只有5個聲望，我需要15個upvote所以... – user1641700