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?
The answers are good, so I just wanted to add a small example. Say you have the following array:
and you want to create a
min heap
. The quickest way to do that is to usemake_heap
algorithm. However, that creates amax heap
by default. In other words, if you call:A
becomes amax heap
. To have amin heap
, on the other hand, you need to add a comparator but do not need to implement one. Instead call the method as follows:This call will make your array a
min heap
.PS:
#include <algorithm>
is necessary to usestd::make_heap
. Same operations apply to thevector
as well.HTH!
You shouldn't need to overload
operator <
forint
(you can't, actually). If you use an external comparator, you should be passing the sameComparator comp
topop_head
as well.* Edit: *
As ildjarn pointed out, your comparison operator does not implement a strict-weak-ordering relation.
Use
std::greater<int>()
as the comparator(to all ofmake_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.