C++中最小堆的比较器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14016921/
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
Comparator for min-heap in C++
提问by Jakob Weisblat
I am trying to make a min-heap1of longs in C++ using the STL make_heap, etc., but my comparator doesn't seem to be comparing properly. The following is my current comparator:
我正在尝试使用 STL等在 C++中制作s的最小堆1，但我的比较器似乎没有正确比较。以下是我目前的比较器：longmake_heap
struct greater1{
bool operator()(const long& a,const long& b) const{
return a>b;
}
};
However, when I do std::pop_heap(humble.begin(),humble.end(),g);where gis an instance of greater1and humbleis a heap who makes [9,15,15,25]when sort_heapis called, I get a 15popped.
但是，当我执行std::pop_heap(humble.begin(),humble.end(),g);where gis an instance of greater1and humbleis a heap who make [9,15,15,25]whensort_heap被调用时，我会15弹出一个。
Is my comparator correct? what might be going wrong?
我的比较器正确吗？可能出什么问题了？
EDIT:
I realized that I am running sort_heap with no comparator, whereas when I run it this comparator, I get [15,15,9,25]from sort_heap. Now I am thinking my comparator is definitely not working, but unsure why.
编辑：
我意识到我在没有比较器的情况下运行 sort_heap，而当我运行这个比较器时，我[15,15,9,25]从sort_heap. 现在我想我的比较器肯定不起作用，但不确定为什么。
1The STL makes a max-heap by default, so I need a comparator.
1默认情况下，STL 生成最大堆，所以我需要一个比较器。
采纳答案by perreal
Perhaps you are missing something somewhere, the code below works as intended:
也许你在某处遗漏了一些东西，下面的代码按预期工作：
#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;
}
回答by zyfo2
just use greater<int>(). it is predefined in std.
只需使用 greater<int>(). 它是在 std 中预定义的。
回答by Dobob
You want to call make_heapon the vector again, not sort_heap. make_heapwill rearrange your entire vector into a min heap given the greater-than comparator whereas sort_heapsorts your element into ascending order and is no longer a heap at all!
您想再次在向量上调用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;
}
