CODEWITHSUNDEEP
c++sortingpriority-queue
Ian
Ian

Reputation: 41

C++, priority queue, items are not sorted

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

Answers (2)

James McNellis
James McNellis

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

Rohit J
Rohit J

Reputation:

Try changing 

return n1.priority() < n2.priority();

to

return n1.priority < n2.priority;

Upvotes: 0

Related Questions