以下比较器在构建最小堆时如何工作？

Question

我知道如果我使用 STL 构建一个堆，它会生成 max_heap。如果我想制作一个 min_heap，我将不得不编写自己的自定义比较器。现在，下面的比较器，

struct greater1{
  bool operator()(const long& a,const long& b) const{
    return a>b;
  }
};

int main() {
  std::vector<long> humble;
  humble.push_back(15);
  humble.push_back(15);
  humble.push_back(9);
  humble.push_back(25);

  std::make_heap(humble.begin(), humble.end(), greater1());
  while (humble.size()) {
    std::pop_heap(humble.begin(),humble.end(),greater1());
    long min = humble.back();
    humble.pop_back();  
    std::cout << min << std::endl;
  }

  return 0;
}

以上代码是我从网上得到的。我只有一个疑问。比较器实际上是如何工作的。据我所知，它不应该是 return a < b 之类的，因为我们希望最小元素在前面，然后是堆中较大的元素。为什么是return a > b。这不是说，if (a>b)，然后这将 return 为真并且 a 将在 b 之前放入堆中，因此更大的元素放在前面更小的元素？

Answer 1

我认为您对比较器语义和堆语义之间的联系读得太多了。请记住，容器的内部细节和结构是故意从您那里抽象出来的，因此，当您开始尝试根据您认为 max_heap 的内部结构应该如何看待这一点来合理化这一点时，您就被带走了。

在标准库中，默认比较器是always less-than。如果特定 container/algorithm 中用于排序的元素之间的关系不是 less-than，则 container/algorithm 将足够聪明地进行转换（在这种情况下，在通常的实现中，通过简单地传递以相反的顺序操作数，如 cmp(b,a)!)。但是，从根本上说，它总是以 less-than 顺序开始，因为这是一致采用的约定。

因此，要反转容器的顺序，您可以使用 less-than 比较器并将其变成 greater-than 比较器，无论容器实现的物理布局如何（在你的意见）原来是。

此外，顺便说一句，为了回应 Croissant 的评论，我会按值取 longs ……事实上，只需使用 std::greater 而不是重新创建它。

Answer 2

标准堆的构建方式是，对于每个元素 a 及其子元素 b，比较 cmp(b,a) 成立，其中 cmp 是提供的比较器。请注意 cmp 的第一个参数是 child。（或者，从内部表示中抽象出来，标准方法是 cmp(top, other) 对于第一个元素 top 和任何其他 other 为真。）

这显然是为了使默认比较器 ("less") 构建最大堆。

因此您需要提供一个比较器，当 child 作为第一个参数提供时，您希望它 return 为真。对于最小堆，这将是 'greater'.

以下比较器在构建最小堆时如何工作？

How does the following comparator even works while building up the min heap?

c++

heap