简介
比较模拟堆和 STL 的优先队列
| a | a | a |
|---|---|---|
| a | a | a |
| a | a | a |
模拟堆和 STL 的优先队列 priority_queue 相同之处在于它们都可以维护极值
实现
模板题1（AcWing.838）
题目描述
输入一个长度为 \(n\) 的整数数列，从小到大输出前 \(m\) 小的数。
样例
in：
5 3
4 5 1 3 2
out：
1 2 3
简单堆实现
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return (f==1)?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
cll n=read();
ll m=read(),len=n,a[N];
inline void down(ll u)
{
ll t=u;
if((u<<1)<=len&&a[u<<1]<a[t]) t=u<<1;
if((u<<1|1)<=len&&a[u<<1|1]<a[t]) t=u<<1|1;
if(u!=t) swap(a[u],a[t]),down(t);
}
inline void up(ll u)
{
while((u>>1)&&a[u>>1]>a[u])
{
swap(a[u>>1],a[u]);
u>>=1;
}
}
int main()
{
for(rll i=1;i<=n;i++) a[i]=read();
for(rll i=(n>>1);i;i--) down(i);
while(m--)
{
write(a[1]),putchar(' ');
a[1]=a[len--],down(1);
}
return 0;
}
模板题2（AcWing.839）
题目描述
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 \(x\)PM，输出当前集合中的最小值DM，删除当前集合中的最小值（数据保证此时的最小值唯一）D k，删除第 \(k\) 个插入的数C k x，修改第 \(k\) 个插入的数，将其变为 \(x\)
现在要进行 \(n\) 次操作，对于所有第 2 个操作，输出当前集合的最小值。
样例
in：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
out：
-10
6
复杂堆实现
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll n=read(),m,len,a[N],ph[N],hp[N];
inline void heap_swap(ll x,ll y)
{
swap(ph[hp[x]],ph[hp[y]]);
swap(hp[x],hp[y]);
swap(a[x],a[y]);
}
inline void down(ll u)
{
ll t=u;
if((u<<1)<=len&&a[u<<1]<a[t]) t=u<<1;
if((u<<1|1)<=len&&a[u<<1|1]<a[t]) t=u<<1|1;
if(u!=t) heap_swap(u,t),down(t);
}
inline void up(ll u)
{
while((u>>1)&&a[u>>1]>a[u])
{
heap_swap(u>>1,u);
up(u>>1);
}
}
int main()
{
while(n--)
{
string op;cin >> op;
if(op=="I")
{
cll x=read();
a[++len]=x;
ph[++m]=len,hp[len]=m;
up(len);
}
else if(op=="PM") write(a[1]),putchar('\n');
else if(op=="DM") heap_swap(1,len--),down(1);
else if(op=="D")
{
cll k=read(),x=ph[k];
heap_swap(x,len--);
up(x),down(x);
}
else if(op=="C")
{
cll k=read(),x=read();
a[ph[k]]=x;
down(ph[k]),up(ph[k]);
}
}
return 0;
}