题外话
其实本身不打算写堆的，主要因为 priority_queue 太香了，但是又怕考场上有一些题目需要手打堆，还是复习一下
堆简介
堆是一种数据结构的总称，本质上是一颗完全二叉树。但它的特殊性质就是两个子节点一定不大于（大根堆）或不小于（小根堆）它们的父节点。这样一来，不难想出，堆顶的元素（根节点）一定是堆中最大（大根堆）或最小（小根堆）的元素。因此，堆常常用来维护序列的最大值或最小值，维护最大值的叫做大根堆，维护最小值的叫做小根堆。
朴素的算法求序列最值，在末尾插入和删除的时间复杂度都为 (Theta(1))，但是求最值的时间复杂度为 (Theta(n))；而堆的插入删除（维护）的时间复杂度为 (Theta(log_2n))，求最值则为 (Theta(1))。所以，堆在维护最值的问题中有广泛运用。
接下来我以线性存储的小根堆为例，讲一下堆的基本操作（红点代表位置待定的点）。
手写堆
虽然 STL 好，但是为了提高对堆的理解，手打堆还是要练习的。
求最值
如图，这是一个堆。
当我们要输出堆的最小元素，就是输出堆顶元素，就是数组中的 (heap[1])：
cout<<heap[1]<<endl;
插入
假如我们要将一个元素 0 插入这个堆里，首先将它插到堆底：
然后我们发现，这样不满足小根堆的性质，就将此元素和它的父节点交换：
交换完，我们发现，还是不能满足性质，就再和父节点交换：
这时，元素满足了性质，插入就完成，元素 0 的位置定下来。
代码实现（while 循环）：
void push(int x)
{
heap[++cnt]=x; //插入堆底，cnt 为堆底指针（变量代替）。
int idx=cnt; //idx 为当前位置（下标）。
while(idx>1) //不为根节点时，判断是否符合性质。
{
if(heap[idx]<heap[idx>>1]) //不符合，就交换。
swap(heap[idx],heap[idx>>1]),idx=idx>>1;
else //否则结束循环，定下位置。
break;
}
}
删除
还以上图为例，加入我们要将 0 删除，首先将 0 与堆底元素交换，并删除交换后的 0：
此时，要删除的元素没有了，但是 4 的位置不符合性质，就将 4 与值较小的子节点交换，这里 4 的子节点中值较小的节点是 1，将它们交换：
此时发现满足性质，4 的位置就可以定下来，交换完成：
代码：
void pop(int x)
{
swap(heap[x],heap[cnt]); //交换元素。
--cnt; //删除。
int idx1=x,swa; //idx1 表示当前节点位置，swa 表示要与其交换的节点的位置。
while((idx1<<1)<=cnt)
{
swa=idx1<<1;
if(heap[swa]>heap[swa+1]&&swa+1<=cnt) //根据左右子节点的大小确定 swa。
swa+=1;
if(heap[swa]<heap[idx1]) //如果不符合性质，就交换。
swap(heap[idx1],heap[swa]),idx1=swa;
else //否则，结束。
break;
}
}
完整操作代码（1 表示插入元素 b，2 表示输出最小元素，3 表示删除下标为 b 的节点）：
#include<bits/stdc++.h>
using namespace std;
long long heap[10000005],cnt,n,a,b;
void push(int x)
{
heap[++cnt]=x;
int idx=cnt;
while(idx>1)
{
if(heap[idx]<heap[idx>>1])
swap(heap[idx],heap[idx>>1]),idx=idx>>1;
else
break;
}
}
void pop(int x)
{
swap(heap[x],heap[cnt]);
--cnt;
int idx1=x,swa;
while((idx1<<1)<=cnt)
{
swa=idx1<<1;
if(heap[swa]>heap[swa+1]&&swa+1<=cnt)
swa+=1;
if(heap[swa]<heap[idx1])
swap(heap[idx1],heap[swa]),idx1=swa;
else
break;
}
}
int main()
{
cin>>n;
for(register int i=0;i<n;++i)
{
cin>>a;
if(a==1)
{
cin>>b;
push(b);
}
if(a==2)
cout<<heap[1]<<endl;
if(a==3)
{
cin>>b;
pop(b);
}
}
}
例题：P3378 【模板】堆 如果想巩固的，可以试试自己打一下例题。
STL 的堆（priority_queue)
priority 是 queue 头文件下的一种容器，翻译为优先队列，可以方面地实现堆。
定义：
对于单个元素的比较，我们可以采取下面这种定义方式：
priority_queue<tepename,vector<tepename>,greater<tepename> > name; //小根堆。
priority_queue<tepename,vector<tepename>,less<tepename> > name; //大根堆。
其中 tepename 为数据类型或标准容器，name 是优先队列的名字。（当类型为字符或字符串，则按字典序比较大小）
但如果我们定义了一个结构体，想按照某种方法比较结构体中的元素来实现堆，那我们就要用一种神奇的操作：重载运算符
假如我们定义了一个结构体 (node)；
struct node
{
int a,b;
};
如果我们想按照 (a) 由大到小，如果 (a) 相同，则按照 (b) 由大到小这种比较方式，那我们可以在结构体中这样重载运算符（其实和 sort 的 cmp 的定义很像）：
struct node
{
int a,b;
bool operator <(const Node &c)const
{
if(a!=c.a)
return a>c.a;
return b>c.b;
}
};
再这样定义 priority_queue：
priority_queue<node> name;
就可以按要求比较了。
函数
-
top() 取堆顶元素。复杂度为 (Theta(1))
-
pop() 删除堆顶元素。复杂度为 (Theta(log_2n))
-
push() 插入一个元素到优先队列中。复杂度为 (Theta(log_2n))
-
size() 返回队列中的元素个数。复杂度为 (Theta(n))
-
empty() 判断队列是否为空。复杂度为 (Theta(1))
例题代码：
那么，上面的例题用 STL 就可以这样：
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n,a,b;
int main()
{
cin>>n;
for(register int i=0;i<n;++i)
{
cin>>a;
if(a==1)
{
cin>>b;
q.push(b);
}
if(a==2)
cout<<q.top()<<endl;
if(a==3)
q.pop();
}
return 0;
}
总结比较
STL 的堆最大的缺点就是只能删除堆顶元素，并且一些操作会受到牵制。所有，考场上如果会手打堆就尽量不用 STL。手打堆的灵活性是 STL 永远比不上的。