1 白话队列(queue)
heap并不归属于STL容器组件，不像队列queue它们拥有自己独立的类定义，它只能借助其他诸如数组，vector等数据结构完成堆的构造操作。但是heap实际当中有很重要的应用，像大家最熟悉的堆排序，所以STL中还是有对应的函数定义的。
接触过堆排序的知道，所谓binary heap 就是一种complete binary tree（完全二叉树），也就是说，整棵binary tree 除了最底层的叶节点之外，是填满的，而最底层的叶节点(s)由左至右又不得有空隙。如下图所示：
#include<algorithm>
using namespace std; 2.2 构建堆
前面说过堆的构建需要借助一个载体，本文中我们围绕vector容器来搭建与处理堆。首先我们来看看堆的构建：
int nArr[10] = {0,2,8,9,1,4,3,7,5,6};
vector<int> vec(nArr,nArr+10); //构建载体vector
make_heap(vec.begin(),vec.end()); //围绕vec构建一个堆。 上面vector初始化的时候保存数据顺序是0,2,8,9,1,4,3,7,5,6，经过堆构建处理最后vector中数据的顺序变成9,7,8,5,6,4,3,2,0,1。新的vector中的数据是完全符合堆的规则的，即前者每个节点的键值都大于或等于其子节点键值，后者的每个节点键值都小于或等于其子节点键值。
2.3 出堆操作
此处出堆操作就是指删除堆中根节点。下图是 pop_heap算法的实际操演情况。既然身为max-heap，最大值必然在根节点。pop操作取走根节点（其实是设至底部容器vector的尾端节点）后，为了满足完全二叉树的条件，必须割舍最下层最右边的叶节点，并将其值重新安插至max-heap（因此有必要重新调整heap结构）。
pop_heap(vec.begin(),vec.end()); // 出堆根节点，将其暂存vector最后一位
vec.pop_back(); // vector删除出堆的数据，即最后一位，现在是8,7,4,5,6,1,3,2,0 2.4 入堆操作
和出堆正好相反，入堆是先将数放置在堆叶节点，并且是由左向右第一个空叶节点，时刻保证是完全二叉树的原则，然后依次上溯。上溯就是将新节点拿来与其父节点比较，如果其键值（key）比父节点大，就父子对换位置。如此一直上溯，直到不需对换或直到根节点为止。过程如下：
vec.push_back(50); // 先添加一个新数据
push_heap(vec.begin(),vec.end()); //再入堆操作 2.5 堆排序操作
堆排序操作的前提也是一样，需要构建堆，然后我们就可以进行堆排序让vector中的数是顺序排列的，通过上面的操作最后的顺序就是0,1,2,3,4,5,6,7,8,50。记住是增序。
sort_heap(vec.begin(),vec.end()); //堆排序 这块解释一下为什么是增序，实际上上面的排序实现就是依靠依次出堆的操作完成的，我们已经知道出堆都会将默认大根节点保存在vector的末尾，所以最终所有的数据就依次在vector中是增序排列的。
3 小结
上面详细的介绍了heap数据结构以及STL中提供的几个与堆有关的方法接口。由于heap的所有元素都必须遵循完全二叉树的排列规则，所以heap不提供遍历功能，也不提供迭代器。
以上是个人学习记录，由于能力和时间有限，如果有错误望读者纠正，谢谢！
转载请注明出处：http://blog.csdn.net/FX677588/article/details/76358777