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;