Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

How to put 3 elements in priority_queue in c++

enter image description here

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?

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading