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

以上是使用自定义比较器为用户定义的数据类型创建最小堆的代码。为什么我们使用 a.rank>b.rank 而不是 a.rank

Answer 1

根据the documentation of std::make_heap的建议，该函数默认构造了一个最大堆。反转比较函数使其构造一个最小堆。

在 C++ 中为结构创建最小堆

creating minheap for structure in c++

c++