I am trying to implement a min heap in c++ for a struct type that I created. I created a vector of the type, but it crashed when I used make_heap on it, which is understandable because it doesn't know how to compare the items in the heap. How do I create a min-heap (that is, the top element is always the smallest one in the heap) for a struct type?
The struct is below:
struct DOC{
int docid;
double rank;
};
I want to compare the DOC structures using the rank member. How would I do this?
I tried using a priority queue with a comparator class, but that also crashed, and it also seems silly to use a data structure which uses a heap as its underlying basis when what I really need is a heap anyway.
Thank you very much, bsg
Simply create your own "functor" for the comparison. Since you want a "min heap" your comparison function should behave like the greater than operator:
#include <iostream>
#include <vector>
#include <algorithm>
struct doc {
double rank;
explicit doc(double r) : rank(r) {}
};
struct doc_rank_greater_than {
bool operator()(doc const& a, doc const& b) const {
return a.rank > b.rank;
}
};
int main() {
std::vector<doc> docvec;
docvec.push_back( doc(4) );
docvec.push_back( doc(3) );
docvec.push_back( doc(2) );
docvec.push_back( doc(1) );
std::make_heap(docvec.begin(),docvec.end(),doc_rank_greater_than());
std::cout << docvec.front().rank << '\n';
}
It's important that you always use the same comparison function in further heap operations.