允許密鑰增加的可變優先級隊列

當實現圖搜索算法時，我需要一個允許優先級更改的優先級隊列。到目前爲止，我一直在使用（detail命名空間，因此沒有記錄），但只是被告知它沒有定義優先級增加（我現在看到的也是在concept documentation中提到的）。允許密鑰增加的可變優先級隊列

所以，我需要找到一個允許增加和減少的結構。我已經嘗試使用vector和push_heap/pop_heap/make_heap，但更新速度太慢。有什麼選擇？我看到助推在待處理（同樣沒有記錄的）目錄中有兩個類，mutable_queue和relaxed_heap，但我只能在五年前的maillist線索中找到它們。他們之間有什麼區別，他們是否允許增加和減少？有沒有任何實施方案未被接受？

來源

2011-09-06 carlpett

Boost.MultiIndex庫的特性容器的操作對象的狀態爲update，並相應地更新索引。

在你的情況下，modify成員函數似乎適合。從文檔：

struct change_name 
{ 
    change_name(const std::string& new_name):new_name(new_name){} 

    void operator()(employee& e) 
    { 
    e.name=new_name; 
    } 

private: 
    std::string new_name; 
}; 

typedef employee_set::index<name>::type employee_set_by_name; 
employee_set_by_name& name_index = es.get<name>(); 

employee_set_by_name::iterator it = name_index.find("Anna Jones"); 
name_index.modify(it,change_name("Anna Smith"));

來源

2011-09-06 07:12:32

將該值放入堆中。您只需修改該值，然後通過向上或向下冒泡來恢復堆不變量。

回想一下，堆本質上是一個二叉樹，其中每個節點都大於它的兩個子節點。

所以，如果你增加一個節點的值，你檢查它是否已經大於其父如果是交換它們，然後重複拉節點向樹根直到節點不再需要交換。

如果你減少了一個節點的值，那麼如果你現在小於你的兩個孩子中最大的一個交換。重複將節點推向樹葉，直至不再需要交換。

來源

2011-09-06 07:10:10

感謝您的意見。然而，我並不太熱衷於自己實現它 - 我強烈懷疑我會創建一個比boost開發者更有效的結構，並且它將用於我的程序的主要部分，因此性能相當重要。你知道任何現有的，經過實地驗證的建議嗎？ – carlpett

允許密鑰增加的可變優先級隊列

回答

相關問題