C++, la file d'attente de priorité, les éléments ne sont pas triés

Question

J'ai un problème avec la file d'attente prioritaire:

std::priority_queue <NodePrio, std::vector<NodePrio>, sortNodesByPrio> PQ; 

où

struct NodePrio 
{ 
Node *node; 
double priority; 

NodePrio() : node(NULL), priority(0) {} 
NodePrio(Node *node_, double priority_) : node(node_), priority(priority_) {} 
}; 

et

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; 
} 

Après avoir poussé à plusieurs reprises de nouveaux éléments

PQ.push(NodePrio(node, distance)); 

et de tout moment ils ne sont pas classés (voir ci-dessous) ... J'ai essayé de déboguer le code, le code comparateur a été à plusieurs reprises effectué ...

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 

Answer 1

Essayez de changer

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

à

return n1.priority < n2.priority; 

Answer 2

sur la base des résultats de l'échantillon « » vous montrer, il semble que vous ne comprenez pas ce qu'est une file d'attente prioritaire est.

Une file d'attente prioritaire garantit que lorsque vous en supprimez des éléments (en utilisant top() et pop()), les éléments seront supprimés dans l'ordre de priorité. Les éléments ne sont pas stockés dans l'ordre de priorité, ils sont stockés dans un tas.

Vous pouvez consulter votre livre d'algorithmes préféré ou votre site Web pour plus d'informations sur la manière dont une file d'attente prioritaire stocke ses éléments.