creating minheap for structure in c++

Question

#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';
}

The above is a code for creating minheap for a user defined data type using custom comparator. why are we using a.rank>b.rank instead of a.rank<b.rank for creating minheap ?

Because otherwise you get a max heap. This is also explained in eg [easy way to maintain a min heap with stl?](https://stackoverflow.com/q/7681779/555045) and other near-duplicates (I did not find a good canonical dupe) — harold, May 28 '22 at 04:17

score 1 · Accepted Answer · answered May 28 '22 at 04:19

1

As suggested by the documentation of std::make_heap, the function constructs a max heap by default. Reversing the comparison function makes it construct a min heap instead.

answered May 28 '22 at 04:19

kotatsuyaki

1,441
3
10
17

creating minheap for structure in c++

1 Answers1