比较在C最小堆++(Comparator for min-heap in C++)

我试图做的最小堆¹ long ++ S IN下，用STL make_heap等，但我比较似乎并不正确比较。 以下是我目前比较：

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

然而，当我这样做std::pop_heap(humble.begin(),humble.end(),g); 其中， g是一个实例greater1和humble是堆谁使[9,15,15,25]当sort_heap被调用时，我得到了15弹出。

是我比较正确的吗？ 可能什么错？

编辑：
我意识到，我没有比较sort_heap运行，而当我运行它这个比较，我得到[15,15,9,25]从sort_heap 。 现在，我想我的比较是绝对不工作，但不确定具体的原因。

¹ STL使默认情况下，最大堆，所以我需要一个比较。

Answer 1:

也许你正在某处失去了一些东西，下面的代码按预期工作：

#include <vector>
#include <algorithm>
#include <iostream>

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;
}

Answer 2:

只是使用greater<int>() 它是在STD预定义。

Answer 3:

你想再次调用make_heap的载体，没有sort_heap。 make_heap将重新安排你的整个向量为特定的最小堆的比大比较而sort_heap排序你的元素升序排列，不再堆在所有！

#include <algorithm>
#include <iostream>
#include <vector>

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

int main()
{
  unsigned int myints[] = {10,20,30,5,15};
  vector<unsigned int> v(myints, myints+5);

  //creates max heap
  std::make_heap(v.begin(). v.end()); // 30 20 10 5 15

  //converts to min heap
  std::make_heap(v.begin(). v.end(), greater1()); // 5 15 10 20 30

  unsigned int s =  v.size();

  //ALSO NEED TO PASS greater1() to pop()!!!
  for(unsigned int i = 0; i < s; i++)
    std::pop_heap(v.begin(). v.end(), greater1()); // popping order: 5 10 15 20 30

  return 0;
}

文章来源: Comparator for min-heap in C++