Reputation: 41
I have a problem with the priority queue:
std::priority_queue <NodePrio, std::vector<NodePrio>, sortNodesByPrio> PQ;
where
struct NodePrio
{
Node *node;
double priority;
NodePrio() : node(NULL), priority(0) {}
NodePrio(Node *node_, double priority_) : node(node_), priority(priority_) {}
};
and
class sortNodesByPrio
{
public:
bool operator () (const NodePrio &n1, const NodePrio &n2) const;
}
bool sortNodesByPrio::operator () (const NodePrio &n1, const NodePrio &n2) const
{
return n1.priority < n2.priority;
}
After repeatedly pushing new elements
PQ.push(NodePrio(node, distance));
and from any point in time they are not sorted (see bellow)... I tried to debug the code, the comparator code has been repeatedly performed...
Step1:
push (node, 55.33);
PQ:
[0] 55.33
Step2:
push (node, 105.91);
PQ:
[0] 105.91
[1] 55.33
Step 3:
push (node, 45.18);
PQ:
[0] 105.91
[1] 55.33
[2] 45.18
Step 4:
push (node, 70.44);
PQ:
[0] 105.91
[1] 70.44
[2] 45.18
[3] 55.33 //Bad sort
Upvotes: 1
Views: 4689
Reputation: 355387
Based on the "sample results" you show, it looks like you don't understand what a priority queue is.
A priority queue guarantees that when you remove elements from it (using top()
and pop()
), the elements will be removed in priority order. The elements are not stored in priority order, they are stored in a heap.
You can consult your favorite algorithms book or website for more information on how a priority queue stores its elements.
Upvotes: 7
Reputation:
Try changing
return n1.priority() < n2.priority();
to
return n1.priority < n2.priority;
Upvotes: 0