c++ - C ++中最小堆的比较器

Question

我正在尝试使用 STL 等在 C++ 中创建 s的最小堆¹，但我的比较器似乎没有正确比较。以下是我目前的比较器：longmake_heap

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

但是，当我执行std::pop_heap(humble.begin(),humble.end(),g);where gis an instance greater1and humbleis a heap who make [9,15,15,25]when sort_heapis called 时，我会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>(). 它是在标准中预定义的。

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