堆是一个完全二叉树，对于小根堆，所有父节点<=子节点，下标就和线段树是一样的
在STL里就是优先队列
只有堆顶元素可以操作（询问或弹出）。
加入新元素时x，heap[++size] = x,下标t=size；
每次比较它和父节点(t/2)的大小，如果它较小就swap。
删除堆顶元素时，用最后一个元素heap[size--]覆盖heap[1]，下标t=1；
每次比较它和左右两个儿子的大小，和较小的swap。
注意：
- 下标t的值不能大于堆的size；
- 我一开始是这么写的：
-
void del() {
swap(heap[],heap[cnt--]);
int t = ;
while(t* <= cnt && (heap[t] > heap[t*] || heap[t] > heap[t*+])) {
if(heap[t*+] < heap[t*] && t*+ <= cnt) {
swap(heap[t],heap[t*+]);
t = t*+;
} else {
swap(heap[t],heap[t*]);
t *= ;
}
}
}把swap(heap[1],heap[cnt--])改为heap[1] = heap[cnt--]就对了
- 如果把最小的数x放到了下面，将最后一个数y从堆顶下移，判断到x的父亲时，一定有x<=y。因为判断是否交换时的条件是左右儿子有一个>y就继续循环，虽然此时判断x的下标>size，但是会默认和另一个儿子交换。
- 如果最后一个值是空的时（为0）就更会翻车了！所以边界条件还是分别判断，这样swap也没问题啦。
代码如下
#include<cstdio>
#include<iostream> using namespace std;
const int maxn = ;
int heap[maxn],n,a,b,cnt; void insert(int x) {
heap[++cnt] = x;
int t = cnt;
while(heap[t] < heap[t/]) {
swap(heap[t],heap[t/]);
t/=;
}
} void del() {
heap[] = heap[cnt--];
int t = ;
while((t* <= cnt && heap[t] > heap[t*]) || (t*+ <= cnt && heap[t] > heap[t*+])) {
if(heap[t*+] < heap[t*] && t*+ <= cnt) {
swap(heap[t],heap[t*+]);
t = t*+;
} else {
swap(heap[t],heap[t*]);
t *= ;
}
}
} int main() {
scanf("%d",&n);
for(int i = ; i <= n; i++) {
scanf("%d",&a);
if(a == ) {
scanf("%d",&b);
insert(b);
}
if(a == ) {
if(cnt)printf("%d\n",heap[]);
}
if(a == ) {
del();
}
}
return ;
}