Can someone explain how std::greater is used to implement priority_queue

Question

std::priority_queue<int, vector<int>, std::greater<int> > pq;

---

I cannot understand the work of std::greater in the priority queue. I am replacing minheap by the priority queue. this code is taken from geeksForGeeks implementation of Prims algorithm using STL

Answer 1

The std::priority_queue type is what’s called a container adapter. It works by starting with a type you can use to represent a sequence, then uses that type to build the priority queue (specifically, as a binary heap). By default, it uses a vector.

In order to do this, the priority queue type has to know how to compare elements against one another in a way that determines which elements are “smaller” than other elements. By default, it uses the less-than operator.

If you make a standard std::priority_queue<int>, you get back a priority queue that

• uses a std::vector for storage, and
• uses the less-than operator to compare elements.

In many cases, this is what you want. If you insert elements into a priority queue created this way, you’ll read them back out from greatest to least.

In some cases, though, this isn’t the behavior you want. In Prim’s algorithm and Dijkstra’s algorithm, for example, you want the values to come back in ascending order rather than descending order. To do this, you need to, in effect, reverse the order of comparisons by using the greater-than operator instead of the less-than operator.

To do this, you need to tell the priority queue to use a different comparison method. Unfortunately, the priority queue type is designed so that if you want to do that, you also need to specify which underlying container you want to use. I think this is a mistake in the design - it would be really nice to just be able to specify the comparator rather than the comparator and the container - but c’est la vie. The syntax for this is

std::priority_queue<int,               // store integers...
                    std::vector<int>,  // ... in a vector ...
                    std::greater<int>> // ... comparing using >