CODEWITHSUNDEEP
c++heap
kancha
kancha

Reputation: 31

min heap in stl without comparator

I have just started using STL and was currently going through heaps. I just wanted to know if there's a way to implement min heap in c++/cpp without comparator.

I tried the following code (a bit modification from geeksforgeeks) :

#include<iostream>
#include<algorithm> // for heap 
#include<vector>
using namespace std;

int main()
{
    // initializing vector;
    vector<int> vi = { 1, 6, 7, 9, 11, 4 };

    make_heap(vi.end(), vi.begin()); // swapped the start and end points

    cout << "The minimum element of heap is : ";
    cout << vi.front() << endl;

}

Output is : 1

I tried this with other test cases as well and it seems to work fine. Just wanted to know if this is logically correct or not? Is it a good practice?

Upvotes: 1

Views: 143

Answers (1)

user4442671
user4442671

Reputation:

First off, your code:

make_heap(vi.end(), vi.begin());

This leads to undefined behavior because vi.end() is a past-the-end iterator. I.E. it does not point to an actual value, and dereferencing it would be illegal.

I think you were attempting to do the following:

make_heap(vi.rbegin(), vi.rend());

But that wouldn't have worked because the resulting heap would still have been a max_heap.

That being said, from the discussion in the comments, OP's question is actually "min heap in stl without writing a comparator", which is subtly different, and leads to a very different answer.

the STL provides ready-made templated comparators in order to handle these cases. The reasoning is that it's much cleaner to have fewer, more flexible algorithms. The lower the API surface, the better.

All you have to do is the following:

make_heap(vi.begin(), vi.end(), std::greater<>());

Upvotes: 2

Related Questions