堆【模板】小根堆堆【模板】大根堆(回)

目录

堆【模板】小根堆

题目描述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);}}
}