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++映射到最小堆

回答

相关问题