C++映射到最小堆

我想知道一種簡單的方法，以獲得在C數據結構 ++C++映射到最小堆

我嘗試這樣一個（最小堆地圖+）：

struct Comp 
{ 
    bool operator()(const pair<int,int>& y , const pair<int,int>& z) 
    { 
     return (y.second < z.second); 
    } 
}; 

priority_queue< pair<int,int> , map<int,int> , Comp > p;

現在我面對的問題因爲它在priority_queue中，我們不能簡單地初始化，就像我們用maps進行初始化一樣。
插入元素的唯一方法是

p.push(make_pair(value1,value2));

我也試圖用簡單的地圖，就不必使用它與priority_queue，但再次問題是，當我試圖找到使用min_element最小元素，它返回的值，而不是這也是必需的關鍵。

請建議以最快的方式執行問題。我也相信有可能超出我的知識。

來源

2016-08-02 Ryuzaki

的'priority_queue'「必須滿足SequenceContainer的要求，其必須迭代此外滿足RandomAccessIterator的要求，它必須提供與通常的語義如下功能的第二個參數：前（）的push_back）（ pop_back（）「--http：//en.cppreference.com/w/cpp/container/priority_queue 。 'std :: map'不符合這些要求。 –

你爲什麼認爲你想要一張地圖+分鐘堆？這是一個[X，Y問題]（http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem） –

@Ryuzaki你想要一種方法來改變一個元素的值（ '對'）在優先級隊列中？你想要一種方法能夠將優先級隊列中的元素編入索引來更改它？ – Shubham

不，您不能對優先級隊列中的元素進行索引以更改值。您必須通過changeKey()操作（可以通過這種方式進行非常優化）自行實施整個優先級隊列，或者執行其他解決方法。

我已經爲Prim的算法實現了一個優先級隊列decreaseKey()來計算最小生成樹。如果你想實施優先隊列，那麼你可以檢查我的回答here或其他一些解決方法檢查加薩的回答here。

來源

2016-08-03 12:39:35 Shubham

非常感謝你 – Ryuzaki

如果您查看第一條評論，並按照priority_queue文檔的鏈接，那麼您將獲得所需的所有工具。

讓我們假設你已經在某處定義了一條邊。比方說

struct edge { 
    int vertex1, vertex2; 
    int weight; 
    bool operator> (const edge &ref) const {return weight > ref.weight;} 
};

你需要一個堆，根據文檔應該是基於向量或deque。我通常更喜歡矢量，但我只是爲了好玩而在這裏放置了雙耳。文檔說使用std ::更大，如果你想有一個最小堆，所以還必須實現邊緣::運算>

#include <queue>  // std::priority_queue and std::deque 
#include <functional> // std::greater 
typedef std::priority_queue<edge, std::deque<edge>, std::greater<edge> > djikstra_heap;

現在你可以推的邊緣，並獲得分鐘。

edge e1{ 1, 2, 2 }; 
edge e2{ 1, 3, 4 }; 

djikstra_heap heap; 
heap.push(e1); 
heap.push(e2); 
edge first_result = heap.top(); heap.pop();

來源

2016-08-03 13:04:16

非常感謝 – Ryuzaki

C++映射到最小堆

回答

相關問題