pop_heap(_RAIter,_RAIter,_Compare)

make_heap()是生成一个堆，大顶堆或小顶堆

• make_heap(_RAIter,_RAIter) 默认生成大顶堆
• make_heap(_RAIter,_RAIter,_Compare) _Compare有两种参数，一种是greater（生成小顶堆），一种是less（生成大顶堆）

push_heap()是向堆中插入一个元素，并且使堆的规则依然成立

• push_heap(_RAIter,_RAIter) 默认为大顶堆
• push_heap(_RAIter,_RAIter,_Compare) _Compare有两种参数，一种是greater（小顶堆），一种是less（大顶堆）
• 调用push_heap之前必须调用make_heap创建一个堆
• 首先数组push_back插入元素，然后再调用push_heap，它会使最后一个元素插到合适位置
• 注意，push_heap中的_Compare和make_heap中的_Compare参数必须是一致的，不然会插入堆失败，最后一个元素还是在最后位置，导致插入失败

pop_heap()是在堆的基础上（即得先构成堆），弹出堆顶元素（还得调用数组pop_back才能完成）。

• pop_heap(_RAIter,_RAIter) 默认为大顶堆
• pop_heap(_RAIter,_RAIter,_Compare) _Compare有两种参数，一种是greater（小顶堆），一种是less（大顶堆）
• 比如pop_heap(nums.begin(), nums.end(),greater<int>())，它会将堆顶元素（即为数组第一个位置）和数组最后一个位置对调，然后你可以调用数组pop_back，删除这个元素
• 注意，pop_heap中的_Compare和make_heap中的_Compare参数必须是一致的，不然会失败

代码示例：

#include <iostream> // std::cout
#include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector> // std::vector
using namespace std;
class Index {
public:
Index(int a, float b) {
i = a;
cost = b;
}
int i;
float cost;
};

struct greater1 {
bool operator()(const Index& a, const Index& b) const {
std::cout <<"operator ,ai ="<< ' ' <<" acost ="<< ' ' << a.cost<<'n';
std::cout <<"operator ,bi ="<< ' ' <<" bcost ="<< ' ' << b.cost<<'n';

return a.cost > b.cost;


}};

struct greater2 {
bool operator()(const Index& a, const Index& b) const {
//return a.cost > b.cost;
std::cout <<"operator ,ai ="<< ' ' <<" acost ="<< ' ' << a.cost<<'n';
std::cout <<"operator ,bi ="<< ' ' <<" bcost ="<< ' ' << b.cost<<'n';
}};

int main()
{
int myints[] = {0,1,2,3,4,5,6,7};
std::vector<Index> v;
v.clear();
for(int i=0;i<8;i++)
v.push_back(Index(i, myints[i]));
std::cout <<"start ,size ="<< ' ' << v.size()<<'n';
for (unsigned i=0; i<v.size(); i++)
std::cout <<i<< ' ' << v[i].cost<< 'n' ;
std::cout << 'n' ;

std::pop_heap(v.begin(), v.end(), greater2());
//std::pop_heap(v.begin(), v.end()); //不重载，编译失败（容器元素是类对象，含有两个成员，需指定）
std::cout <<"pop_heap no grearter "<<'n';
for (unsigned i=0; i<v.size(); i++)
std::cout <<i<< ' ' << v[i].cost<< 'n' ;
std::cout << 'n' ;

std::pop_heap(v.begin(), v.end(), greater2());
std::cout <<"pop_heap no grearter "<<'n';
for (unsigned i=0; i<v.size(); i++)
std::cout <<i<< ' ' << v[i].cost<< 'n' ;
std::cout << 'n' ;

std::pop_heap(v.begin(), v.end(), greater2());
std::cout <<"pop_heap no grearter "<<'n';
for (unsigned i=0; i<v.size(); i++)
std::cout <<i<< ' ' << v[i].cost<< 'n' ;
std::cout << 'n' ;

std::pop_heap(v.begin(), v.end(), greater1());
std::cout <<"pop_heap grearter "<<'n';
for (unsigned i=0; i<v.size(); i++)
std::cout <<i<< ' ' << v[i].cost<< 'n' ;
std::cout << 'n' ;

std::pop_heap(v.begin(), v.end(), greater1());
std::cout <<"pop_heap grearter "<<'n';
for (unsigned i=0; i<v.size(); i++)
std::cout <<i<< ' ' << v[i].cost<< 'n' ;
std::cout << 'n' ;
v.pop_back();

std::pop_heap(v.begin(), v.end(), greater1());
std::cout <<"pop_heap grearter "<<'n';
for (unsigned i=0; i<v.size(); i++)
std::cout <<i<< ' ' << v[i].cost<< 'n' ;
std::cout << 'n' ;

return 0;
}

 

运行结果：

start ,size = 8
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7

operator ,ai =  acost = 2
operator ,bi =  bcost = 1
operator ,ai =  acost = 4
operator ,bi =  bcost = 3
operator ,ai =  acost = 3
operator ,bi =  bcost = 7
operator ,ai =  acost = 1
operator ,bi =  bcost = 7
pop_heap no grearter 
0 7
1 1
2 2
3 3
4 4
5 5
6 6
7 0

operator ,ai =  acost = 2
operator ,bi =  bcost = 1
operator ,ai =  acost = 4
operator ,bi =  bcost = 3
operator ,ai =  acost = 3
operator ,bi =  bcost = 0
operator ,ai =  acost = 1
operator ,bi =  bcost = 0
pop_heap no grearter 
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7

operator ,ai =  acost = 2
operator ,bi =  bcost = 1
operator ,ai =  acost = 4
operator ,bi =  bcost = 3
operator ,ai =  acost = 3
operator ,bi =  bcost = 7
operator ,ai =  acost = 1
operator ,bi =  bcost = 7
pop_heap no grearter 
0 7
1 1
2 2
3 3
4 4
5 5
6 6
7 0

operator ,ai =  acost = 2
operator ,bi =  bcost = 1
operator ,ai =  acost = 4
operator ,bi =  bcost = 3
operator ,ai =  acost = 3
operator ,bi =  bcost = 0
operator ,ai =  acost = 1
operator ,bi =  bcost = 0
pop_heap grearter 
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7

operator ,ai =  acost = 2
operator ,bi =  bcost = 1
operator ,ai =  acost = 4
operator ,bi =  bcost = 3
operator ,ai =  acost = 3
operator ,bi =  bcost = 7
pop_heap grearter 
0 1
1 3
2 2
3 7
4 4
5 5
6 6
7 0

operator ,ai =  acost = 2
operator ,bi =  bcost = 3
operator ,ai =  acost = 5
operator ,bi =  bcost = 6
pop_heap grearter 
0 2
1 3
2 5
3 7
4 4
5 6
6 1