I been studying priority_queue in c from Leetcode and I found this code from solution I understand that this is minimum heap but don't understand how is this storing 3 elements to minHeap.

1. is vector<int> gets matrix[r][0], vector<vector<int>> gets r and greater<> gets 0????
2. Why do we need to put priority_queue<int,vector<int>,greater<int>> minHeap a vector<int> to make Minimum heap?

CodePudding user response：

First, let's look at the meaning of the template arguments in the class of minHeap.

From cppreference:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
class priority_queue;

Template parameters

T - The type of the stored elements. ...

Container - The type of the underlying container to use to store the elements. ...

Compare - A Compare type providing a strict weak ordering.

So, for minHeap, it contains vector<int> objects. It uses a vector<vector<int>> as the underlying storage to contain these vector<int> objects. And it uses greater<> to compare two vector<int> objects to decide what order they go in.

What does the greater<> signify? The Compare argument is used to decide which element goes on top. By default, priority_queue uses less<>, which means that larger elements go on top. By using greater<> instead, it flips the direction of the comparison, so smaller elements go on top. This is what makes it a "min" heap.

Now, looking at the call to push:

void push( const value_type& value );
void push( value_type&& value ); (since C  11)

push is only accepting a single argument, and the argument is of type value_type, which in this case is vector<int>.

So the line

minHeap.push({matrix[r][0], r, 0});

Is actually adding a single vector<int> to minHeap. The values contained in that vector<int> are matrix[r][0], r, and 0.