pop

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::vectorusing 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 = 80 01 12 23 34 45 56 67 7operator ,ai = acost = 2operator ,bi = bcost = 1operator ,ai = acost = 4operator ,bi = bcost = 3operator ,ai = acost = 3operator ,bi = bcost = 7operator ,ai = acost = 1operator ,bi = bcost = 7pop_heap no grearter 0 71 12 23 34 45 56 67 0operator ,ai = acost = 2operator ,bi = bcost = 1operator ,ai = acost = 4operator ,bi = bcost = 3operator ,ai = acost = 3operator ,bi = bcost = 0operator ,ai = acost = 1operator ,bi = bcost = 0pop_heap no grearter 0 01 12 23 34 45 56 67 7operator ,ai = acost = 2operator ,bi = bcost = 1operator ,ai = acost = 4operator ,bi = bcost = 3operator ,ai = acost = 3operator ,bi = bcost = 7operator ,ai = acost = 1operator ,bi = bcost = 7pop_heap no grearter 0 71 12 23 34 45 56 67 0operator ,ai = acost = 2operator ,bi = bcost = 1operator ,ai = acost = 4operator ,bi = bcost = 3operator ,ai = acost = 3operator ,bi = bcost = 0operator ,ai = acost = 1operator ,bi = bcost = 0pop_heap grearter 0 01 12 23 34 45 56 67 7operator ,ai = acost = 2operator ,bi = bcost = 1operator ,ai = acost = 4operator ,bi = bcost = 3operator ,ai = acost = 3operator ,bi = bcost = 7pop_heap grearter 0 11 32 23 74 45 56 67 0operator ,ai = acost = 2operator ,bi = bcost = 3operator ,ai = acost = 5operator ,bi = bcost = 6pop_heap grearter 0 21 32 53 74 45 66 1

转载于:https://www.cnblogs.com/Baron-Lu/p/6677042.html