定义：
堆的底层数据结构是树，一般不引起歧义的情况下，堆指的是二叉堆，其底层数据结构是完全二叉树，堆分为大根堆和小根堆，大根堆的每个节点的父亲都大于当前节点，小根堆反之，本文以小根堆为例
二叉堆插入
思路：将要插入的树放在数组最后，令数组原来的大小为 \(size\) ，堆数组的名为 \(heap\) ，则 \(heap[++size]=x\) ，其中 \(x\) 为要插入的数字，之后将插入的数字不断向上调整即可（如图）
CODE:
void put(int x){
heap[++size]=x;
int now=size;
while (now>1&&heap[now/2]>heap[now]){
swap(heap[now/2],heap[now]);
now/=2;
}
}
时间复杂度： \(O(\log n)\)
二叉堆删除
思路：将要删除的元素与最后一个元素交换，同时 \(size--\) ，再将这个位置的树向下调整
CODE:
void del(int idx){
swap(heap[size],heap[idx]);
size--;
while (idx*2<=size){
int t=idx;
idx*=2;
if (idx+1<=size&&heap[idx]>heap[idx+1]) idx++;
if (heap[idx]>=heap[t]) return ;
swap(heap[t],heap[idx]);
}
}
时间复杂度： \(O(\log n)\)
例题
[NOIP2004 提高组] 合并果子
例题代码：
点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;
int n,heap[10005],size,ans;
void put(int x){
heap[++size]=x;
int now=size;
while (now>1&&heap[now/2]>heap[now]){
swap(heap[now/2],heap[now]);
now/=2;
}
}
void del(int idx){
swap(heap[size],heap[idx]);
size--;
while (idx*2<=size){
int t=idx;
idx*=2;
if (idx+1<=size&&heap[idx]>heap[idx+1]) idx++;
if (heap[idx]>=heap[t]) return ;
swap(heap[t],heap[idx]);
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
int tmp;
scanf("%d",&tmp);
put(tmp);
}
for (int i=1;i<n;i++){
int a=heap[1];
del(1);
int b=heap[1];
del(1);
put(a+b);
ans+=a+b;
}
printf("%d",ans);
return 0;
}