使用stl维护最小堆的简单方法？

Question

对于用户定义的结构,据我所知,这很容易.只是重载操作员<.但是,对于int/float等..,我真的需要重载operator <for int吗？这是我尝试过的:

       #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会不能正确维护min-heap？有没有更简单的方法来实现这一目标？谢谢!

编辑:对不起,我没仔细检查手册.是的,将comp传递给pop_heap或push_heap应该可以解决问题.但是,你是什么意思,我不应该使用外部比较器？如果这不是正确的方法,那么实现这一目标的常用方法是什么？

Answer 1

使用std::greater<int>()的比较(所有的make_heap,push_heap,pop_heap).这()很重要 - std::greater<int>是一个函子类而不是函数,所以你需要一个它的实例.

Answer 2

答案很好,所以我只想添加一个小例子.假设您有以下数组:

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于此.

HTH!

Answer 3

你不应该需要重载operator <的int(你不能,实际上).如果你使用外部比较器,你也应该将它传递Comparator comp给pop_head它.

*编辑:*

正如ildjarn所指出的,你的比较运算符没有实现严格弱顺序关系.

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