C++中用于最小堆的比较器

Question

我正在尝试使用C++中的STL make_heap等工具来创建一个¹由long类型组成的小根堆，但我的比较器似乎不能正确地进行比较。以下是我的当前比较器：

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是一个堆，调用sort_heap时生成[9,15,15,25]，我会弹出一个15。

我的比较器是否正确？可能出了什么问题？

编辑：
我意识到我在没有比较器的情况下运行sort_heap，而当我使用这个比较器运行它时，我从sort_heap得到[15,15,9,25]。现在我在想我的比较器肯定不起作用，但不确定原因。

¹STL默认生成最大堆，所以我需要一个比较器。

- Jakob Weisblat

---

你在使用相同的比较器来进行 make_heap 操作吗？ - perreal

我在使用make_heap时使用了相同的比较器，但是刚意识到我可能没有在sort_heap中使用它。 - Jakob Weisblat

你所说的“working”样例代码是什么意思？ - Jakob Weisblat

请原谅我如果我说错了，我不太擅长C/C++，但是const long& a和const long& b不是表示指向常量值的指针吗？因此将a与b进行比较就是在比较这些值的地址？ - Zéychin

@Zéychin 这是传递引用。它们会自动取消引用。一个 * 会使它成为指针。 - Jakob Weisblat

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

- perreal

---

由于某种原因，在多次添加和删除“greater1（）”到我的调用后，它现在可以工作了。也许它生成了编译器错误，我没有注意到（我有一个脚本运行“g++ file.cpp;./a.out”），并且在我删除错误后最终编译成功。谁知道呢。无论如何，由于您对解决我的问题有所帮助，我接受了这个答案。 - Jakob Weisblat

谢谢，也许你的意思是将 std::push_heap(humble.begin(),humble.end(),greater1()); 放在 if 块内。 - perreal

我确实想把它放在那里。很好的发现。这解释了我的错误，但不是我最新的错误（“非法文件打开（/dev/tty）”）。 - Jakob Weisblat

g++ file.cpp && ./a.out - Joshua

Answer 2

只需使用greater<int>()。它在std中预定义。

- zyfo2

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

- Dobob