user268451 user268451 - 2 months ago 13x
C++ Question

easy way to maintain a min heap with stl?

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];

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

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?

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?


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