我的优先级队列有问题:
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;
}
在反复 push 新元素之后
PQ.push(NodePrio(node, distance));
并且从任何时候开始,它们都没有被排序(请参见下面)...我试图调试代码,比较器代码已被重复执行...
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
最佳答案
根据显示的“样本结果”,您似乎不了解什么是优先级队列。
优先级队列保证当您从中删除元素时(使用top()
和pop()
),这些元素将按照优先级顺序被删除。元素没有按优先级顺序存储,而是存储在堆中。
您可以查阅自己喜欢的算法书籍或网站,以获取有关优先级队列如何存储其元素的更多信息。