C ++优先级队列未排序 [英] C++ priority queue does not sort

问题描述

我试图使用自定义的Class and Compare结构在C ++中实现优先级队列，但是每当我推送一个新元素时，该队列都不会对其进行排序.

I tried to implement a priority queue in C++ with a custom Class and Compare struct, but whenever I push a new element the queue doesn´t sort itself.

在标题中:

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

结构:

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

有什么想法吗?

推荐答案

您的代码正确.但是我认为您在这里有一个误会.因为priority_queue是使用数据结构堆实现的.众所周知，堆没有排序.它仅具有最大元素的属性在前面.每次将元素插入堆时，堆将使用O(lgN)是时候将最大值推到最前面了.每次您弹出一个元素时，都会获得最大的元素.但是堆根本没有排序.

Your code is correct. But I think you have a misunderstanding here. Because priority_queue is implemented using data structure heap. As we know, heap is not sorted. It only has the property that the maximum element is at the front. Every time, you insert an element into a heap, heap will use O(lgN) time to push the maximum into the front. And every time you pop an element, the largest element will be obtained. But heap is not sorted at all.

这篇关于C ++优先级队列未排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！