mercredi 29 avril 2015

Implementing Min priority Queue(C++ STL) using user-defined objects

I am implementing Prims Algorithm. I have a vector of Edges along with their weights. The problem is, after inserting, the queue does not remain in increasing order according to weight of edges.

The relevant code is given below:-

struct weightcomp // To be used solely for priority Queue...
{
    bool operator()(Edge &E1, Edge &E2)
    {
        if(E1.weight > E2.weight)
            return true;
    }
};

std::priority_queue<Edge,std::vector<Edge>,weightcomp> PQ; // Priority Queue for Edges

void visit(std::vector<Edge> &PMST, int i) // PMST = Vector of edges and i = name of node
{
    for(auto iter = PMST.begin();iter != PMST.end();++iter)
    {
        if((*iter).u == i || (*iter).v == i)
        {
            PQ.push((*iter));
            (*iter).del = true;  // Mark the vectors elements to be removed.
        }
    }

    PMST.erase(std::remove_if(PMST.begin(),PMST.end(),[](Edge e){ return e.del;}),PMST.end()); // Delete the marked elements
}

What am I missing in the implementation?

Aucun commentaire:

Enregistrer un commentaire