Initializing and Inserting into a Priority Queue (C++)

Question

I've never used the STL C++ priority queue before and I find the details on the website a little confusing.

I want to create a priority queue of Nodes, which I have defined as:

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

I also to insert into the queue in ascending order based on the weight of the nodes. However, I don't know how many nodes will be in the final PQ.

I'm confused about which constructor to use to create the PQ. At the moment, I have:

std::priority_queue<Node> myQueue;

But since I want the queue to sort based on the weights of the nodes, should I use the constructor:

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

Would that work? Would "Node" by the ctnr in that case?

Finally, when I want to push an element into the priority_queue (using the STL priority_queue::push), will the element automatically be placed in the right location?

Thank you.

Answer 1

The initialization doesn't determine how the priority queue operates. If you want it to sort a particular way, you have two options.

The first option is to define the < operator on your Node objects to compare them the way you want.

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;

The second option is to define a custom comparator type and specify it as a template argument:

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

You can use :

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;  

when I want to push an element into the priority_queue (using the STL priority_queue::push), will the element automatically be placed in the right location?

Yes .

Hope this helps and don't confuse !