Инициализация и вставка в очередь приоритетов (C++)

Question

Я никогда раньше не использовал приоритетную очередь STL C++, и я нахожу детали на веб-сайте немного запутанными.

Я хочу, чтобы создать приоритет очереди узлов, которые я определил, как:

struct Node { 
    string data; 
    int weight; 
    Node *left, *right; 
} 

Я также вставить в очереди в порядке возрастания на основе веса узлов. Тем не менее, я не знаю, сколько узлов будет в финальном PQ.

Я смущен тем, какой конструктор использовать для создания PQ. На данный момент у меня есть:

std::priority_queue<Node> myQueue; 

Но так как я хочу очередь для сортировки на основе весов узлов, я должен использовать конструктор:

priority_queue (const Compare& comp, const Container& ctnr); 

будет работать? Будет ли «узел» в ctnr в этом случае?

Наконец, когда я хочу нажать элемент в priority_queue (используя STL priority_queue :: push), будет ли элемент автоматически размещаться в нужном месте?

спасибо.

Answer 1

Инициализация не определяет, как работает очередь приоритетов. Если вы хотите, чтобы он сортировал конкретный путь, у вас есть два варианта.

Первый вариант заключается в определении оператора < на ваших объектах Node, чтобы сравнить их так, как вы хотите.

struct Node { 
    string data; 
    int weight; 
    Node *left, *right; 
    bool operator<(const Node& n) const { 
     return weight < n.weight; 
     // or "weight > n.weight" if you want the smallest weight at the top 
    } 
}; 
std::priority_queue<Node> myQueue; 

Второй вариант заключается в определении пользовательского типа компаратора и указать его в качестве аргумента шаблона:

struct NodeComp { 
    bool operator()(const Node& n1, const Node& n2) const { 
     return n1.weight < n2.weight; 
     // or "n1.weight > n2.weight" if you want the smallest weight at the top 
    } 
}; 
std::priority_queue<Node, std::vector<Node>, NodeComp> myQueue; 

Answer 2

Вы можете использовать:

struct cmp 
{ 
    bool operator() (Node const &a, Node &b) { return a.weight < b.weight; } 
}; 
typedef std::priority_queue<Node, std::vector<Node>,cmp> My_queue; 

, когда я хочу, чтобы подтолкнуть элемент в priority_queue (с использованием STL priority_queue :: толчок), будет элемент автоматически помещается в нужном месте?

Да.

Надеюсь, что это поможет и не смущает!