C++ 使用stl维护最小堆的简单方法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7681779/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
easy way to maintain a min heap with stl?
提问by user268451
for user defined struct, as I understand, it's easy. Just overload the operator <. However, for int/float etc.., do I really need to overload operator < for int? Here is what I tried:
对于用户定义的结构，据我所知，这很容易。只需重载运算符 <。但是，对于 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;
}
the results are:
结果是：
initial min heap : 5
5 10 30 20 15
30 10 15 20
now pop_heap, push_heap won't maintain the min-heap correctly? is there any easier way to achieve this? Thanks!
现在 pop_heap、push_heap 不会正确维护最小堆？有没有更简单的方法来实现这一目标？谢谢！
Edit: sorry, I didn't check the manual carefully. yes, passing comp to pop_heap or push_heap should do the trick. However, what do you mean, I should not use an external comparator? If it's not the right way, what's the common way to achieve this?
编辑：对不起，我没有仔细检查手册。是的，将 comp 传递给 pop_heap 或 push_heap 应该可以解决问题。但是，你的意思是，我不应该使用外部比较器？如果这不是正确的方法，那么实现这一目标的常用方法是什么？
采纳答案by K-ballo
You shouldn't need to overload operator <for int(you can't, actually). If you use an external comparator, you should be passing the same Comparator compto pop_headas well.
你不应该需要超负荷operator <的int（你不能，实际上）。如果您使用外部比较器，您也应该将其传递Comparator comp给pop_head。
* Edit: *
* 编辑： *
As ildjarn pointed out, your comparison operator does not implement a strict-weak-ordering relation.
正如 ildjarn 指出的那样，您的比较运算符没有实现严格的弱排序关系。
a < b ? false : true; --> a >= b
b < a ? true : false; --> a > b
回答by Steve Jessop
Use std::greater<int>()as the comparator(to all of make_heap, push_heap, pop_heap). The ()are important - std::greater<int>is a functor class not a function, so you need an instance of it.
使用std::greater<int>()的比较（所有的make_heap，push_heap，pop_heap）。将()是重要的-std::greater<int>是一个函数子类不是一个函数，所以你需要它的一个实例。
回答by erol yeniaras
The answers are good, so I just wanted to add a small example. Say you have the following array:
答案很好，所以我只想添加一个小例子。假设您有以下数组：
array<int, 10> A{5,2,8,3,4,1,9,12,0,7};
and you want to create a min heap. The quickest way to do that is to use make_heapalgorithm. However, that creates a max heapby default. In other words, if you call:
并且您想创建一个min heap. 最快的方法是使用make_heap算法。但是，max heap默认情况下会创建一个。换句话说，如果你打电话：
make_heap(A.begin(), A.end());
Abecomes a max heap. To have a min heap, on the other hand, you need to add a comparator but do not need to implement one. Instead call the method as follows:
A成为max heap. min heap另一方面，要拥有，您需要添加一个比较器但不需要实现一个比较器。而是按如下方式调用该方法：
make_heap(A.begin(), A.end(), greater<int>());
This call will make your array a min heap.
此调用将使您的数组成为min heap.
PS: #include <algorithm>is necessary to use std::make_heap.
Same operations apply to the vectoras well.
PS：#include <algorithm>有必要使用std::make_heap. 同样的操作也适用于vector。
HTH!
哼！
