如何使用STL实现Prim的算法？
我试图实现一个堆和无序映射的组合的数据结构。 堆将保存包含标识符和成本的图节点。 我使用min_extract函数在log（n）时间内让节点继续展开。 [我正在使用std :: vector和std :: make_heap，pop_heap等从算法中实现堆]
无序映射保存节点，在矢量映射中的位置。 无序映射用于支持包含和更新节点函数。 但是对于我来说，我需要节点和它在矢量中的位置之间的映射，否则我不得不对该节点进行线性搜索。
更令人担忧的是，在我推送或弹出某个项目并调用push_heap或pop_heap的情况下，这将围绕向量中的节点以及我在地图中保留的位置进行转换，最终会出错。
那么如何实现功能，我可以在哪里维护节点与其位置之间的映射。
void push(T elem) // This will 0(n)... As the element has to be found
{
heapVec_.push_back(elem); // add tp vec
std::push_heap<compar_> (heapVec_.begin() , heapVec_.end());
// sort ? or just find in the vec ?
std::size_t pos = 0 ;
// find position of the item in the vector
std::find_if(heapVec_.begin() , heapVec_.end() , [&pos , &elem](const T& item)
{
if(item == elem)
{
return true;
}
else
{
++pos;
}
});
// add to map
heapMap_.emplace_back(elem , pos); // how to keep track of the element where this object is added to ?
}
我正在寻找的数据结构必须支持：find min：O（lg n）包含：O（1）update-node：O（lg n）insert：O（lg n）
如果我在自己的堆上展开自己的堆，那么在实现气泡上下移动时，我会更新地图中节点的位置，这将会很简单。 在我这样做之前，我想确保我不能在STL中做到这一点。
如果您将边缘放入优先级队列而不是节点中，那么您不需要该更新节点功能，并且一切都变得更加容易。
然后：
将一个初始顶点添加到该集合，并将其边缘添加到优先级队列
从优先队列中删除最便宜的边E.
如果E的顶点V之一不在树中，则将E和V添加到树中。 V会进入你的设定。 如果V对于不在集合中的节点有任何边缘，则将这些边缘添加到优先级队列中。
回到第2步，直到队列为空。