easy way to maintain a min heap with stl?

Question

for user defined struct, as I understand, it's easy. Just overload the operator <. However, for int/float etc.., do I really need to overload operator < for int? Here is what I tried:

       #include <iostream>
       #include <algorithm>
       #include <vector>
       using namespace std;

       bool comp(const int& a, const int& b)
       {
          return a<b?false:true;
       }

       int main () 
       {
         int myints[] = {10,20,30,5,15};
         vector<int> v(myints,myints+5);
         vector<int>::iterator it;
         make_heap(v.begin(), v.end(), comp);
         cout << "initial min heap   : " << v.front() << endl;
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;

         pop_heap (v.begin(),v.end());
         v.pop_back();
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;
       }

the results are:

        initial min heap   : 5
        5 10 30 20 15
        30 10 15 20

now pop_heap, push_heap won't maintain the min-heap correctly? is there any easier way to achieve this? Thanks!

Edit: sorry, I didn't check the manual carefully. yes, passing comp to pop_heap or push_heap should do the trick. However, what do you mean, I should not use an external comparator? If it's not the right way, what's the common way to achieve this?

score 33 · Answer 1 · answered Oct 07 '11 at 00:19

33

Use std::greater<int>() as the comparator(to all of make_heap, push_heap, pop_heap). The () are important - std::greater<int> is a functor class not a function, so you need an instance of it.

answered Oct 07 '11 at 00:19

Steve Jessop

273,490
39
460
699

score 23 · Answer 2 · answered Jul 03 '16 at 19:47

The answers are good, so I just wanted to add a small example. Say you have the following array:

array<int, 10> A{5,2,8,3,4,1,9,12,0,7};

and you want to create a min heap. The quickest way to do that is to use make_heap algorithm. However, that creates a max heap by default. In other words, if you call:

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

A becomes a max heap. To have a min heap, on the other hand, you need to add a comparator but do not need to implement one. Instead call the method as follows:

make_heap(A.begin(), A.end(), greater<int>());

This call will make your array a min heap.

PS: #include <algorithm> is necessary to use std::make_heap. Same operations apply to the vector as well.

HTH!

K-ballo · Accepted Answer · 2011-10-07T00:17:53.367

9

You shouldn't need to overload operator < for int (you can't, actually). If you use an external comparator, you should be passing the same Comparator comp to pop_head as well.

* Edit: *

As ildjarn pointed out, your comparison operator does not implement a strict-weak-ordering relation.

a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b

edited Oct 07 '11 at 00:17

answered Oct 07 '11 at 00:00

K-ballo

80,396
20
159
169

1

The larger issue is that his comparator is equivalent to `int`'s `operator>=`, which is not a strict-weak-ordering comparator, and thus illegal. – ildjarn Oct 07 '11 at 00:02
sorry, I didn't check the manual carefully. yes, passing comp to pop_heap or push_heap should do the trick. However, what do you mean, I should not use an external comparator? If it's not the right way, what's the common way to achieve this? – user268451 Oct 07 '11 at 00:07
2

@user268451 : You can use an external comparator if you wish, but it must implement a strict-weak-ordering relation, so logic equivalent to `operator>=` is not allowed but logic equivalent to `operator<` or `operator>` is. See this excellent article for more info, authored by one of the very fathers of modern C++: [Order I Say!](http://cpp-next.com/archive/2010/02/order-i-say/) – ildjarn Oct 07 '11 at 00:09
@user268451: I may have gotten it wrong, but doesn't the default `operator<` give you the order you intend? – K-ballo Oct 07 '11 at 00:10
@K-ballo:default operator < give you a max-heap, max int on the top; I wanna a min heap, min int on the top; so I think you mean the correct comparator for my case is: return a>=b?true:false; – user268451 Oct 07 '11 at 00:14
@user268451: No, with = in it is no strict order, I think what you need is `b < a`. – K-ballo Oct 07 '11 at 00:17
1

@user268451 : You should just get rid of your custom comparator altogether and use `std::greater()` instead. – ildjarn Oct 07 '11 at 00:20
@ildjarn: You should really put all the information you gave in the form of a complete answer, it would certainly be better than mine. – K-ballo Oct 07 '11 at 00:21
@K-ballo : Your answer includes its comments, so your answer is good IMO. :-] – ildjarn Oct 07 '11 at 00:22
@ildjarn: thanks for the article link and all your comments. I'm still new to stl and that article seems very difficult for me to understand. – user268451 Oct 07 '11 at 00:39
@K-ballo: could you put the whole and right definition of bool comp function in your answer? I still not getting why return a – user268451 Oct 07 '11 at 00:41
2

@user268451: suppose `a == b`. Then `a – Steve Jessop Oct 07 '11 at 00:49

easy way to maintain a min heap with stl?

3 Answers3

Linked