STL 中与heap 有关的操作有 如下几个 :
make_heap(), pop_heap(),
push_heap(), sort_heap(), is_heap;
is_heap() :
原型如下 :
1.bool is_heap(iterator
start, iterator
end);
->判断迭代器[start, end] 区间类的元素是否构成一个堆. 是返回true,否则返回false.
2.bool
is_heap(iterator
start, iterator
end, StrictWeakOrdering
cmp);
->判断迭代器[start, end] 区间类的元素在cmp条件下是否构成一个堆.
是返回true ,否则返回 false.
make_heap() :
原型如下 :
1.void
make_heap(
random_access_iterator start,
random_access_iterator end
);
2.void
make_heap(
random_access_iterator start,
random_access_iterator end,
StrictWeakOrdering cmp
);
->以 迭代器[start , end]区间内的元素生成一个堆. 默认使用 元素类型 的<（即less<type>） 操作符
进行判断堆的类型, 因此生成的是大顶堆 ，即vector是从小到大排序.
->当使用了 版本2时, 系统使用 用户定义的cmp函数来构建一个堆。对type类型，可以在第三个参数传入greater<type>()得到最小堆。
->值得注意的是, make_heap 改变了 迭代器所指向 容器的值.
pop_heap() :
要先调用pop_heap()再在容器中删除数据
原型如下 :
1.void
pop_heap(
random_access_iterator start,
random_access_iterator end
);
2.void
pop_heap(
random_access_iterator start,
random_access_iterator end,
StrictWeakOrdering cmp);
->pop_heap() 并不是真的把最大（最小）的元素从堆中弹出来.而是重新排序堆. 它把首元素和末元素交换，然后将[first,last-1)的数据再做成一个堆。
此时, 原来的首元素 位于迭代器end-1 的位置,它已不再属于堆的一员!
->如果使用了 版本2 , 在交换了首元素和末元素后 ,使用 cmp 规则 重新构建一个堆.
push_heap() :
要先在容器中加入数据，再调用push_heap ()
原型如下 :
1.void
push_heap(
random_access_iterator start,
random_access_iterator end
);
2.void
push_heap(
random_access_iterator start,
random_access_iterator end,
StrictWeakOrdering cmp);
-> 算法假设迭代器区间[start, end-1)内的元素已经是一个有效堆, 然后把end-1
迭代器所指元素加入堆，接着再调整堆，使其满足堆的特性.
-> 如果使用了 cmp 参数, 将使用 cmp 规则构建堆.
sort_heap() :
原型如下 :
1.void
sort_heap
(random_access_iterator start,
random_access_iterator end);
2.void
sort_heap
(random_access_iterator start,
random_access_iterator end,
StrictWeakOrdering cmp);
-> 堆结构被完全破坏, 相当于对元素进行排序, 效果和排序算法类似.
-> 如果使用了 cmp 参数, 将使用 cmp 规则排序堆.
先来讲解一下堆的初始化即调整过程：
堆的定义是：n个元素的序列{k1,k2,…,kn}，当且仅当满足如下关系时被成为堆
(1)Ki <= k2i 且 ki <= k2i-1
或 (2) Ki >= k2i 且 ki >= k2i-1
(i = 1,2,…[n/2])
当满足(1)时，为最小堆，当满足(2)时，为最大堆。
若将此序列对应的一维数组堪称是一个完全二叉树，则2i和2i+1个节点分别是节点i的左右子节点。
如下为一个最大堆：
下面以最小堆为例说明堆的输出：
图1为一个最小堆，当最小节点根节点13输出后，将最后一个节点97作为根节点，移到顶端，如图2. 然后要对堆进行调整。比较此完全树的根节点与其两个子节点大小，因为27 < 38 < 97，所以27是三个节点里最小的，将节点27与根节点97交换。此时以97替代27而产生的右子树为一个新的堆，再以97为根节点，对此最小堆进行调整，同理，知道要将97与49交换，得到图3的完全树。此时以97代替49为根节点的右子树为一个新堆，再对此堆做同样的操作，因为此完全树已经是最小堆，所以可以停止操作，堆的调整完毕。此时再将根节点，对的最小值输出，并进行同样的调整，可以得到如图4的新堆。这个过程被称为“筛选”。
同样以最小堆说明堆的初始化：
从一个无序序列初始化为一个堆的过程就是一个反复“筛选”的过程。由完全二叉树的性质可以知，一个有n个节点的完全二叉树的最后一个非叶节点是节点[n/2]，堆的初始化过程就从这个[n/2]节点开始。上图为如下无序数组的初始化：
{49,38,65,97,76,13,27,50}
首先，未处理的数组对应的堆为图1模样。从第四个节点开始（[8/2]=4），因为50 < 97，故要交换两节点，交换后还要继续对其新的左子树进行类似的调整。易见其左子树只有节点97，已经为最佳情况，故可以继续堆的初始化，如图2。再考虑第三个节点，因为13 < 27 < 65，即节点13为当前的最小节点，故与节点65交换，并对新的左子树进行调整，其也为最佳情况，故可继续堆的初始化，结果如图3。然后考虑第二个节点，因为38
< 50 < 76，故已经为最优情况，不用调整。最后再考虑第一个节点，根节点。因为 13 < 38 < 49，故需要将根节点49与其右孩子节点13交换，交换后还要继续对其新的右子树进行类似调整，可见右子树还需要调整，因为 27 < 49 < 65,故将节点49与节点27交换。此时已经处理完了根节点，初始化结束。最终结果如图5.
堆中进行的操作主要是：插入，删除，以及初始化。
下面只讨论最大堆。
在最大堆中进行插入操作，例如在下图所示的左边的最大堆中进行插入，插入后结构应该是和右边的图一样的。
插入时，先将新元素插入到最后一个叶子节点的后面，然后先和自己的父节点开始比较，也就是先从2所在结点开始比较，如果小于父节点的值，那么就直接作为孩子结点插入，如果大于，那么就要现将父节点下移，然后再和父节点的父节点比较，一直比较到根节点为止，所以插入过程，是从叶节点到根的一条路径。
最大堆的删除，从最大堆的删除时，该元素从根部移出。删除后，此时堆需要重新构造，以便于仍然为完全二叉树。例如下图：
先将根节点的值20取出后，为了结构仍然是二叉树，所以直接将最后一个结点，也就是保存2的结点去掉，然后将2的值保存下来，然后呢，就从根节点的两个孩子开始比较，看看2 根的左右孩子，这三个元素中，谁最大，那么根节点的值就是谁，然后就将2和空出来的结点的左右孩子(如果有的话)比较，确认子树的根节点的值，这样一步一步确认下去。
代码：
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
void PrintfVectorInt(vector<int> &vet)
{
for (vector<int>::iterator pos = vet.begin(); pos != vet.end(); pos++)
printf("%d ", *pos);
putchar('\n');
}
int main()
{
const int MAXN = 20;
int a[MAXN];
int i;
for (i = 0; i < MAXN; ++i)
a[i] = rand() % (MAXN * 2);
//动态申请vector 并对vector建堆
vector<int> *pvet = new vector<int>(20);
pvet->assign(a, a + MAXN);
//建堆
make_heap(pvet->begin(),pvet->end()); //建立最大堆，，根节点大于叶节点
PrintfVectorInt(*pvet);
pvet->push_back(25);
push_heap(pvet->begin(),pvet->end()); //最大堆，根节点大于叶节点
PrintfVectorInt(*pvet);
pop_heap(pvet->begin(),pvet->end());
pvet->pop_back();
PrintfVectorInt(*pvet);//最大堆，根节点大于叶节点
sort_heap(pvet->begin(),pvet->end()); //相当于对数组排序，最大堆已经被破坏
PrintfVectorInt(*pvet);//从小到大的有序数列
delete pvet;
return 0;
}
