C++ min heap with user-defined type

Question

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

Contagious

what's your definition of "it crashed"? Surely, if you don't have any comparison functor or operator< function you'll be getting compilation errors. – Crumbly

No, I didn't, actually. Definitely not with the priority queue, which had an overloaded operator defined, and I don't think with the make_heap, either. Though it could be that in the latter case I did get a compilation error. The first time, though, it compiled fine but crashed at runtime. – Contagious

If you try to use make_heap with two arguments only, you have to have an operator< for your struct type. If you don't, you'll get compilation errors. Simple as that. – Crumbly

Answer 1

Add a comparison operator:

struct DOC{

    int docid;
    double rank;
    bool operator<( const DOC & d ) const {
       return rank < d.rank;
    }
};

Structures can almost always usefully have a constructor, so I would also add:

DOC( int i, double r ) : docid(i), rank(r) {]

to the struct as well.

Indigenous

As far as I can tell this would lead to a "max heap". But he wants a "min heap" which requires a functor that returns true if and only if the first argument is greater than the second. – Crumbly

Thank you very much! I ended up using a priority queue, because it had more of the functions that I needed, but I created a constructor and overloaded the < and > operators as you showed and it worked! – Contagious

@bsg, if "it worked" that way, you asked the wrong question and a "max heap" is what you wanted. Make up your mind. – Crumbly

@sellbitze To switch the state of the heap he only needed to switch the sense of the test. – Indigenous

As sellbitze said, I changed the direction of the test around. – Contagious

Answer 2

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.

Crumbly