使用STL来维护小根堆的简便方法是什么？

Question

对于用户自定义的结构体，我了解到很容易实现。只需要重载运算符<即可。但是对于int/float等基本类型，我真的需要重载运算符<吗？以下是我的尝试：

       #include <iostream>
       #include <algorithm>
       #include <vector>
       using namespace std;

       bool comp(const int& a, const int& b)
       {
          return a<b?false:true;
       }

       int main () 
       {
         int myints[] = {10,20,30,5,15};
         vector<int> v(myints,myints+5);
         vector<int>::iterator it;
         make_heap(v.begin(), v.end(), comp);
         cout << "initial min heap   : " << v.front() << endl;
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;

         pop_heap (v.begin(),v.end());
         v.pop_back();
         for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
         cout<<endl;
       }

结果如下：

        initial min heap   : 5
        5 10 30 20 15
        30 10 15 20

现在使用pop_heap和push_heap无法正确地维护最小堆？有更简单的方法吗？ 谢谢！

编辑： 抱歉，我没有仔细查看手册。是的，将comp传递给pop_heap或push_heap应该可以解决问题。但是，你说不应该使用外部比较器？如果这不是正确的方法，那么通常达成这个目的的方式是什么？

- user268451

Answer 1

在所有的make_heap，push_heap和pop_heap中使用std::greater<int>()作为比较器。这里的()很重要 - std::greater<int>是一个函数对象类而不是一个函数，因此您需要一个它的实例。

- Steve Jessop

Answer 2

答案很好，我只想再添加一个小例子。假设你有以下数组：

array<int, 10> A{5,2,8,3,4,1,9,12,0,7};

如果你想创建一个 最小堆，最快的方法是使用 make_heap 算法。然而，默认情况下这会创建一个 最大堆。换句话说，如果你调用：

make_heap(A.begin(), A.end());

A变成了一个最大堆。而要创建一个最小堆，则需要添加比较器但不需要实现它。可以按以下方式调用方法：

make_heap(A.begin(), A.end(), greater<int>());

调用此函数将使您的数组成为 最小堆。

附注：#include <algorithm> 在使用 std::make_heap 时是必需的。 同样的操作也适用于向量。

希望对你有所帮助！

- erol yeniaras

Answer 3

你不应该为 int 过载 operator <（实际上是无法过载的）。如果你使用外部比较器，你应该将相同的 Comparator comp 传递给 pop_head。* 编辑：* 如 ildjarn 指出的那样，你的比较运算符并没有实现严格的弱序关系。

a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b

- K-ballo

---

更大的问题是他的比较器等同于 int 的 operator>=，这不是一个严格弱序比较器，因此是非法的。 - ildjarn

抱歉，我没有仔细查看手册。是的，将comp传递给pop_heap或push_heap应该可以解决问题。但是，你说我不应该使用外部比较器？如果这不是正确的方法，那么通常实现这个功能的方式是什么？ - user268451

@user268451：如果你愿意，可以使用外部比较器，但它必须实现严格弱序关系，因此不允许逻辑等价于operator> =，但逻辑等价于operator <或operator>是可以的。请参阅这篇由现代C++之父之一撰写的出色文章，获取更多信息：Order I Say！ - ildjarn

@user268451：您应该彻底放弃自定义比较器，改用std::greater<int>()。 - ildjarn

假设 a == b。那么 a<b?false:true 是 true。这是错误的，根据 C++03 的 25.3/4 规定，比较器必须具有对于所有 x 都满足 !comp(x,x) 的属性。然而，b<a?true:false 是 false，所以这是正确的。 - Steve Jessop