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

之后，并且从任何时间点它们都没有排序（见下文）...我尝试调试代码，比较器代码已被重复执行...

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

根据您显示的“示例结果”，您似乎不了解优先级队列是什么。

优先级队列保证当您从其中删除元素（使用 top() 和 pop()）时，元素将按优先级顺序删除。元素不按优先级顺序存储，而是存储在堆中。

您可以查阅您最喜欢的算法书籍或网站，以获取有关优先级队列如何存储其元素的更多信息。

Answer 2

尝试更改

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

为

return n1.priority < n2.priority;