堆【模板】小根堆堆【模板】大根堆(回)
目录
堆【模板】小根堆
题目描述1
输入1
输出1
样例输入 1
样例输出 1
提示1
代码1
堆【模板】大根堆
题目描述2
输入
输出
样例输入2
样例输出2
提示2
代码2
堆【模板】小根堆
题目描述1
初始小根堆为空，我们需要支持以下3种操作：
操作1： 1 x 表示将x插入到堆中(1e-6<=x<=1e6)
操作2： 2 输出该小根堆内的最小数，若小根堆为空，则输出empty
操作3： 3 删除该小根堆内的最小数，若小根堆为空，则输出err
输入1
第一行包含一个整数N，表示操作的个数
接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：
操作1： 1 x
操作2： 2
操作3： 3
输出1
包含若干行，根据题意输出。
样例输入 1
12
1 5
2
3
3
2
1 -5
1 7
1 -9
2
2
1 -17
2
样例输出 1
5
err
empty
-9
-9
-17
提示1
数据规模：
对于30%的数据：N<=20
对于70%的数据：N<=10000
对于100%的数据：N<=10^6
样例说明：
12
1 5
2 输出堆顶5
3 删除5
3 删堆顶时堆为空，输出err
2 取堆顶时堆为空，输出empty
1 -5
1 7
1 -9
2 输出堆顶-9
2 输出堆顶-9
1 -17
2 输出堆顶-17
代码1
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i,fl,x,t,a[1000100];
void up(int t){
int fa;
while(t!=1){
fa=t/2;
if(a[fa]>a[t])
swap(a[t],a[fa]),t=fa;
else break;
}
}
void down(int tt){
int son;
while(tt*2<=t){
son=tt*2;
if(son+1<=t&&a[son+1]<a[son])son++;
if(a[son]<a[tt])
swap(a[son],a[tt]),tt=son;
else break;
}
}
main(){
cin>>n;
for(i=1;i<=n;i++){
cin>>fl;
if(fl==1){
cin>>x;
a[++t]=x;
up(t);
}
else if(fl==2){
if(t==0)cout<<"empty\n";
else cout<<a[1]<<"\n";
}
else{
if(t==0)cout<<"err\n";
else a[1]=a[t],t--,down(1);
}
}
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i,fl,x,t,a[1000100];
void up(int t){int fa;while(t!=1){fa=t/2;if(a[fa]>a[t])swap(a[t],a[fa]),t=fa;else break;}
}
void down(int tt){int son;while(tt*2<=t){son=tt*2;if(son+1<=t&&a[son+1]<a[son])son++;if(a[son]<a[tt])swap(a[son],a[tt]),tt=son;else break;}
}main(){cin>>n;for(i=1;i<=n;i++){cin>>fl;if(fl==1){cin>>x;a[++t]=x;up(t);}else if(fl==2){if(t==0)cout<<"empty\n";else cout<<a[1]<<"\n";}else{if(t==0)cout<<"err\n";else a[1]=a[t],t--,down(1);}}
}堆【模板】大根堆
题目描述2
初始大根堆为空，我们需要支持以下3种操作：
操作1： 1 x 表示将x插入到堆中(1e-6<=x<=1e6)
操作2： 2 输出该大根堆内的最大数，若大根堆为空，则输出empty
操作3： 3 删除该大根堆内的最大数，若大根堆为空，则输出err
输入
第一行包含一个整数N，表示操作的个数
接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：
操作1： 1 x
操作2： 2
操作3： 3
输出
包含若干行，根据题意输出。
样例输入2
12
1 5
2
3
3
2
1 -5
1 7
1 -9
2
2
1 217
2样例输出2
5
err
empty
7
7
217提示2
数据规模：
对于30%的数据：N<=20
对于70%的数据：N<=10000
对于100%的数据：N<=10^6
样例说明：
12
1 5
2 输出堆顶5
3 删除5
3 删堆顶时堆为空，输出err
2 取堆顶时堆为空，输出empty
1 -5
1 7
1 -9
2 输出堆顶7
2 输出堆顶7
1 217
2 输出堆顶217
代码2
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll i,j,a[600100],n,q,x,t,a1,T,a2,a3,fl;
void up(int t){
int fa;
while(t!=1){
fa=t/2;
if(a[fa]<a[t])
swap(a[fa],a[t]),t=fa;
else break;
}
}
void down(int fa){
int son;
while(fa*2<=t){
son=fa*2;
if(son+1<=t&&a[son+1]>a[son])son++;
if(a[fa]<a[son])swap(a[fa],a[son]),fa=son;
else break;
}
}
main(){
cin>>n;
for(i=1;i<=n;i++){
cin>>fl;
if(fl==1){
cin>>x;
a[++t]=x;
up(t);
}
else if(fl==2){
if(t==0)cout<<"empty\n";
else cout<<a[1]<<"\n";
}
else{
if(t==0)cout<<"err\n";
else a[1]=a[t],t--,down(1);
}
}
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll i,j,a[600100],n,q,x,t,a1,T,a2,a3,fl;
void up(int t){int fa;while(t!=1){fa=t/2;if(a[fa]<a[t])swap(a[fa],a[t]),t=fa;else break;}
}
void down(int fa){int son;while(fa*2<=t){son=fa*2;if(son+1<=t&&a[son+1]>a[son])son++;if(a[fa]<a[son])swap(a[fa],a[son]),fa=son;else break;}
}
main(){cin>>n;for(i=1;i<=n;i++){cin>>fl;if(fl==1){cin>>x;a[++t]=x;up(t);}else if(fl==2){if(t==0)cout<<"empty\n";else cout<<a[1]<<"\n";}else{if(t==0)cout<<"err\n";else a[1]=a[t],t--,down(1);}}
}