Очередь приоритетов C++ не сортируется

Question

Я пытался реализовать приоритетную очередь в C++ с помощью пользовательской структуры Class и Compare, но всякий раз, когда я нажимаю новый элемент, очередь не сортируется сама.

В заголовке:

private:
    std::priority_queue<Node*, std::vector<Node*>, NodeCompare> queue;

Struct:

struct NodeCompare
{
    bool operator()(Node* n1, Node* n2) 
    {
        int val1 = n1->getValue();
        int val2 = n2->getValue();
        return val1 < val2;
    }
};

В классе:

Node* node = new Node(nrInTree, value);
queue.push_back(node);

Есть идеи?

Answer 1

Ваш код правильный. Но я думаю, что у вас здесь недоразумение. Потому что priority_queue реализован с использованием кучи структуры данных. Как известно, куча не отсортирована. Он обладает только тем свойством, что максимальный элемент находится спереди. Каждый раз, когда вы вставляете элемент в кучу, куча будет использовать время O(lgN), чтобы протолкнуть максимум вперед. И каждый раз, когда вы выталкиваете элемент, будет получен самый большой элемент. Но куча вообще не сортируется.