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.
- is
vector<int>getsmatrix[r][0],vector<vector<int>>getsrandgreater<>gets0???? - Why do we need to put
priority_queue<int,vector<int>,greater<int>> minHeapavector<int>to make Minimum heap?
>Solution :
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.
