简介
二叉堆的逻辑结构是一颗完全二叉树，然而它的实现却是用一维数组实现的。
二叉堆分小根堆和大根堆。
对于小根堆中的结点 x，其子树的所有结点键值均大于 x，即值越小的越靠近根结点，根结点的优先级最高。（大根堆同理）
二叉堆常用于解决一些队列模拟问题，或用在其他算法中进行优化。
运行原理（手写）
对于二叉堆中的结点，假设其编号为 x，则 x 的左子树下标是 ，x 的右子树下标是 .
因此我们通过简单的计算即可访问堆中结点的子结点。
初始化
对于堆中的元素，将其初始化为优先级最低的值。比如 INF 或 -INF
插入
假设堆的大小为 ，则 进行如下的操作
- 把 v 插入队尾，.
- 循环比较 v 和 v 的父结点，如果 v 的优先级更高，就将他们交换；否则结束循环
由此，完成插入操作
弹出（堆顶）
假设堆的大小为 size，则 进行如下的操作
- 把根结点赋值为优先级最小的值
- 直接把数组末尾的元素调至堆顶的位置（不是复制），.
- 循环比较 v 和 v 的左右子结点，将三个结点中优先级最高的与 v 交换；如果 v 本身就是最高的，结束循环
由此，完成弹出操作
代码实现
#define INF 0x3f3f3f3f
int heap[4000001],heap_size;
int n,a,x;
void heap_push(int v) {heap[++heap_size]=v;
for(int i=heap_size; i>1; i>>=1) {if(heap[i>>1]>heap[i])heap[i>>1]^=heap[i]^=heap[i>>1]^=heap[i];
}
}
void heap_pop() {heap[1]=heap[heap_size],heap[heap_size]=INF,heap_size--;
int i=1;
while(i<heap_size) {if(heap[i]<=heap[i<<1]&&heap[i]<=heap[i<<1|1])break;
if(heap[i<<1]<heap[i<<1|1])heap[i<<1]^=heap[i]^=heap[i<<1]^=heap[i],i<<=1;
else heap[i<<1|1]^=heap[i]^=heap[i<<1|1]^=heap[i],i=i<<1|1;}
}
int heap_top(){return heap[1];}
bool heap_empty(){return (bool)heap_size;}
STL 优先队列
- 头文件：
<queue> - 声明：
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; - 基本操作
重载运算符
- 在用结构体作为优先队列的元素时，须重载
<符号：struct data{ int a,b; bool operator<(data tht)const{return this->a>tht.a; } }; - 这里的小于是指优先级小于后者。也就是说，如果函数返回值为真，则
*this的优先级小于tht的优先级，所以tht会比*this更优先出队. - 函数参数列表后面的 const 表示这个函数不会修改任何成员变量的值（这种 const 只对成员函数有效），是 priority_queue 重载
<时必须有的。
对顶堆
某些题目要求维护一个有序的序列，并动态输出其中的一个值。这时为了保证序列的有序，使用一个大根堆和一个小根堆分两边维护，中间建立一个变量记录当前的答案
[POJ3784]Running Median
动态维护中位数
对顶堆模拟即可
思路就是一个大根堆一个小根堆，中间一个变量存储当前中位数。每次输入数据，调整一下两个堆的元素，输出中间的变量即可
#include<cstdio>
#include<queue>
using namespace std;
int T,s,n,ai;
priority_queue<int> p;
priority_queue<int,vector<int>,greater<int> > q;
void solve(){scanf("%d%d",&s,&n);
printf("%d %d",s,n/2+1);
while(!q.empty())q.pop();
while(!p.empty())p.pop();
int cur;
for(int i=1;i<=n;i++){scanf("%d",&ai);
if(i==1)cur=ai;
else if(ai<cur)p.push(ai);
else q.push(ai);
if(i%2){while(p.size()>q.size())q.push(cur),cur=p.top(),p.pop();
while(p.size()<q.size())p.push(cur),cur=q.top(),q.pop();
if(i%20==1)puts("");
printf("%d",cur);
}
}
puts("");
}
int main(){scanf("%d",&T);
while(T--)solve();
return 0;
}
[LuoguP1801] 黑匣子
典型的对顶堆维护
#include<cstdio>
#include<queue>
using namespace std;
const int N=200005;
int m,n,a[N];
int mid=0x3f3f,id;
priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int> p;
void add(int v){if(mid==0x3f3f)mid=v;
else if(mid<v)q.push(v);
else p.push(v);
}
int get(){while(p.size()<id)p.push(mid),mid=q.top(),q.pop();
while(p.size()>id)q.push(mid),mid=p.top(),p.pop();
++id;
return mid;
}
int main(){scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
int cur=0;
for(int i=1;i<=n;i++){int u;
scanf("%d",&u);
while(cur<u)add(a[++cur]);
printf("%d\n",get());
}
return 0;
}
[POJ2442]Sequence
个长度为 的序列，每个序列各选一个数相加，可以得到 个和
求最小的 个和
分析
考虑两个序列 .
先从小到大排序
显然
因此考虑二插堆，处理完堆顶，就把堆顶之后推出的两个和入堆。
问题在于， 和 都可以转到 ，因此要避免重复入堆
于是我们限制入堆决策
对于 ，
时，将 入堆
仅当 且 时，将 入堆
最后，对于 个序列，用数学归纳法，将前 个序列的前 小和作为一个序列，与第 个序列一起求两个序列的前 小和。相当于两两求前 小和即可
复杂度 .
代码
//POJ2442
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100005;
int n,m,T,a[N],b[N],t[N];
struct data{
int x,y;
bool operator<(data da)const{return a[x]+b[y]>a[da.x]+b[da.y];}
};
priority_queue<data> q;
void merge(){while(!q.empty())q.pop();
q.push((data){1,1});
for(int i=1;i<=n;i++){data k=q.top();q.pop();
t[i]=a[k.x]+b[k.y];
if(k.y<n)q.push((data){k.x,k.y+1});
if(k.x<n&&k.y==1)q.push((data){k.x+1,k.y});
}
for(int i=1;i<=n;i++)a[i]=t[i];
}
int main(){scanf("%d",&T);
while(T--){scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<m;i++){for(int j=1;j<=n;j++)scanf("%d",&b[j]);
sort(b+1,b+n+1);
merge();}
for(int i=1;i<=n;i++)printf("%d",a[i]);
puts("");
}
return 0;
}
[LuoguP2085] 最小函数值
个二次函数，限定定义域为正整数（），问最小的 个函数值
分析
数学 + 二插堆
显然，开口向上，否则问题无解
于是，找到对称轴（四舍五入），从对称轴一个个加入元素即可
注意定义域
代码
#include<cstdio>
#include<queue>
using namespace std;
const int N=10004;
int n,m;
int a[N],b[N],c[N],r[N];// 四舍五入的对称轴
struct data{
int fi,x,v;
bool operator<(data d)const{return v>d.v;}
};
priority_queue<data> q;
int f(int fi,int pos){return a[fi]*pos*pos+b[fi]*pos+c[fi];};
int main(){scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);
double ri=b[i]/(-2.0*a[i]);// 对称轴
r[i]=(int)ri+(ri-(int)ri<0.5?0:1);
q.push((data){i,max(r[i],1),f(i,max(r[i],1))});
}
for(int i=1;i<=m;i++){data k=q.top();q.pop();
printf("%d",k.v);
if(k.x==r[k.fi]){q.push((data){k.fi,k.x+1,f(k.fi,k.x+1)});
if(k.x>1)q.push((data){k.fi,k.x-1,f(k.fi,k.x-1)});
}
else if(k.x>r[k.fi])q.push((data){k.fi,k.x+1,f(k.fi,k.x+1)});
else if(k.x>1)q.push((data){k.fi,k.x-1,f(k.fi,k.x-1)});
}
return 0;
}
[LuoguP1484] 种树
一个长度为 n 的序列，选不超过 k 个互不相邻的数，使总和最大
同 BZOJ1150
分析
双向链表 + 二插堆
如果只选一个数，显然选最大的
如果选两个数，会出现两种情况：
最大和次大都选（不相邻）
选最大数两边的数（如果只选一边的数，那么将这个数换成最大数可以使结果更优，故两边的数都选）
因此我们选了一个数 ，就把它前后一共三个结点合并成一个结点，标记权值为
每次我们取出堆顶，累加到答案，再合并堆顶两边的结点。这样如果之后的操作有一次累加到了 ，相当于把 抵消，总和变成 .
对于结点的合并，删除，用双向链表和二插堆同步维护即可
代码
#include<cstdio>
#include<queue>
using namespace std;
const int N=500005;
int n,m,c[N],pre[N],nex[N];
bool del[N];// 延时删除
long long ans;
struct data{
long long v;int idx;
bool operator<(data d)const{return v<d.v;}
};
priority_queue<data> q;
int main(){scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&c[i]);
pre[i]=i-1,nex[i]=i+1;// 双向链表
q.push((data){c[i],i});
}
for(int i=1;i<=m;i++){
data k;
do{k=q.top();q.pop();}while(del[k.idx]);
if(k.v<0)break;
ans+=k.v;
c[k.idx]=k.v=c[pre[k.idx]]+c[nex[k.idx]]-k.v;
// 删点
if(pre[k.idx]!=0)del[pre[k.idx]]=1,pre[k.idx]=pre[pre[k.idx]];
if(nex[k.idx]!=n+1)del[nex[k.idx]]=1,nex[k.idx]=nex[nex[k.idx]];
nex[pre[k.idx]]=k.idx;
pre[nex[k.idx]]=k.idx;
q.push((data){k.v,k.idx});// 新结点入堆
}
printf("%lld",ans);
return 0;
}
![[SDOI2009]HH 的项链](/medias/featureimages/7.jpg)