easy way to maintain a min heap with stl?

user268451 picture user268451 · Oct 7, 2011 · Viewed 23.5k times · Source

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?

Answer

Steve Jessop picture Steve Jessop · Oct 7, 2011

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.