二叉堆的定义
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：
由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。
堆的存储
一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
下面再介绍STL中与堆相关的4个函数——建立堆make_heap()，在堆中添加数据push_heap()，在堆中删除数据pop_heap()和堆排序sort_heap()：
头文件 #include <algorithm>
下面的_First与_Last为可以随机访问的迭代器（指针），_Comp为比较函数（仿函数），其规则——如果函数的第一个参数小于第二个参数应返回true，否则返回false。
建立堆
make_heap(_First, _Last, _Comp)
默认是建立最大堆的。对int类型，可以在第三个参数传入greater<int>()得到最小堆。
在堆中添加数据
push_heap (_First, _Last)
要先在容器中加入数据，再调用push_heap ()
在堆中删除数据
pop_heap(_First, _Last)
要先调用pop_heap()再在容器中删除数据
堆排序
sort_heap(_First, _Last)
排序之后就不再是一个合法的heap了
下面给出STL中heap相关函数的使用范例：
- //by MoreWindows( http://blog.csdn.net/MoreWindows )
- #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>(40);
- pvet->assign(a, a + MAXN);
- //建堆
- make_heap(pvet->begin(), pvet->end());
- PrintfVectorInt(*pvet);
- //加入新数据 先在容器中加入，再调用push_heap()
- pvet->push_back(25);
- push_heap(pvet->begin(), pvet->end());
- PrintfVectorInt(*pvet);
- //删除数据 要先调用pop_heap()，再在容器中删除
- pop_heap(pvet->begin(), pvet->end());
- pvet->pop_back();
- pop_heap(pvet->begin(), pvet->end());
- pvet->pop_back();
- PrintfVectorInt(*pvet);