堆的模板题

注意要使用小根堆

其实STL又好用又好写
逃

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+7;
namespace Heap {//使用命名空间让代码更易懂
    int h[N];//小根堆
    ll tot=0;//节点数
  
    void update(ll now) {
        while(now){
            if(h[now/2]>h[now])
                swap(h[now/2],h[now]);
            else 
                break;
            now/=2;
        }
        return ;
    }//节点向上修改
    void pushup(int x) {
        h[++tot]=x;
        update(tot);
        return ;
    }//新建节点

  void pop() {
        ll pos=1;
        swap(h[pos],h[tot--]);
        while(pos*2<=tot){
            ll minn=pos*2;
            if(minn+1<=tot&&h[minn+1]<h[minn])minn++;//判断右子节点是否更优
            if(h[minn]>h[pos])break;
            swap(h[minn],h[pos]);
            pos=minn;
        }
        return ;
    }//弹出节点
}
int n;
int main(){
    cin>>n;
    while(n--){
        int opt;
        cin>>opt;
        if(opt==1){
            int add;
            cin>>add;
            Heap::pushup(add);
        }
        if(opt==2){
            cout<<Heap::h[1]<<'\n';
        }
        if(opt==3){
            Heap::pop();
        }
    }
    return 0;
}