C++, 우선 순위 큐는 항목 내가 우선 순위 큐에 문제가

Question

을 정렬되지 않습니다 :

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

곳

struct NodePrio 
{ 
Node *node; 
double priority; 

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

및

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

반복적으로 새로운 요소를 누른 후를

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

그들이 (우는 소리 참조)으로 정렬되지 않습니다 어떤 시점에서 617,451,515,... 난

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

변화 시도 ... 코드, 비교기 코드가 반복적으로 수행 된 디버깅하려고

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

"샘플 결과"를 바탕으로

return n1.priority < n2.priority; 

Answer 2

에 당신이 보여, 당신이 우선 순위 큐가 무엇인지 이해하지 못하는 것 같습니다.

우선 순위 큐를 사용하면 (top() 및 pop()을 사용하여) 요소를 제거 할 때 요소가 우선 순위에 따라 제거됩니다. 요소는 우선 순위에 저장되지 않고 힙에 저장됩니다.

우선 순위 큐가 요소를 저장하는 방법에 대한 자세한 정보는 좋아하는 알고리즘 서적이나 웹 사이트를 참조하십시오.