在C++中创建minheap

yi0zb3m4  于 2024-01-09  发布在  其他
关注(0)|答案(1)|浏览(156)
  1. #include <vector>
  2. #include <algorithm>
  3. struct doc {
  4. double rank;
  5. explicit doc(double r) : rank(r) {}
  6. };
  7. struct doc_rank_greater_than {
  8. bool operator()(doc const& a, doc const& b) const {
  9. return a.rank > b.rank;
  10. }
  11. };
  12. int main() {
  13. std::vector<doc> docvec;
  14. docvec.push_back( doc(4) );
  15. docvec.push_back( doc(3) );
  16. docvec.push_back( doc(2) );
  17. docvec.push_back( doc(1) );
  18. std::make_heap(docvec.begin(),docvec.end(),doc_rank_greater_than());
  19. std::cout << docvec.front().rank << '\n';
  20. }

字符串
上面是一个使用自定义比较器为用户定义的数据类型创建minheap的代码。为什么我们使用a.rank>b.rank而不是a.rank<b.rank来创建minheap?

inn6fuwd

inn6fuwd1#

正如the documentation of std::make_heap所建议的,函数默认构造一个max heap。反转比较函数会使其构造一个min heap。

相关问题