19

据我了解，对于用户定义的结构，这很容易。只需重载运算符 <。但是，对于 int/float 等，我真的需要为 int 重载 operator < 吗？这是我尝试过的：

       #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 应该可以解决问题。但是，您是什么意思，我不应该使用外部比较器？如果这不是正确的方法，那么实现这一目标的常用方法是什么？

4

3 回答 3

31

用作std::greater<int>()比较器（对所有make_heap, push_heap, pop_heap）。()很重要 -std::greater<int>是函子类而不是函数，因此您需要它的实例。

于 2011-10-07T00:19:53.000 回答
21

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

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

并且您想创建一个min heap. 最快的方法是使用make_heap算法。但是，默认情况下会创建一个max heap。换句话说，如果你打电话：

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

A变成一个max heap. 另一方面，要拥有min heap一个比较器，您需要添加一个比较器，但不需要实现一个。而是按如下方式调用该方法：

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

此调用将使您的数组成为min heap.

PS：#include <algorithm>是必须要用的std::make_heap。同样的操作也适用于vector。

！

于 2016-07-03T19:47:08.613 回答
9

你不应该需要超载operator <（int实际上你不能）。如果您使用外部比较器，您也应该将其传递Comparator comp给pop_head。

* 编辑： *

正如 ildjarn 指出的那样，您的比较运算符没有实现严格的弱排序关系。

a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b
于 2011-10-07T00:00:57.377 回答