左偏树

#include <iostream>
using namespace std;
const int maxn = 1e6+5;
int val[maxn]; //原序列 
int ch[maxn][3], fa[maxn], dis[maxn] = {-1};
int root; //堆的根，等于0表示堆的空的，一个堆有一个根 
inline int getroot(int x){
    while(fa[x])    x = fa[x];
    return x;
}
inline int merge(int x, int y){//合并两个堆 
    if(x == 0) return y;
    if(y == 0) return x;
    if(val[x] > val[y])  swap(x, y);
    ch[x][1] = merge(ch[x][1], y);
    fa[ch[x][1]] = x;
    if(dis[ch[x][0]] < dis[ch[x][1]]) std::swap(ch[x][0], ch[x][1]);
    dis[x] = dis[ch[x][1]] + 1;
    return x;
}
void remove(int x){//删除节点，x不是根节点 
    int fx = fa[x], p = merge(ch[x][0], ch[x][1]);
    int &ls = ch[fx][0], &rs = ch[fx][1];
    fa[p] = fx;
    ls == x? ls = p: rs = p;
    while(p){
        if(dis[ls] < dis[rs])    swap(ls, rs);
        if(dis[fx] == dis[rs] + 1)  return;
        dis[fx] == dis[rs] + 1;
        p = fx, fx = fa[x];
        ls = ch[fx][0], rs = ch[fx][1];
    }
}
void rmvroot(int &x){//删根节点，x为根节点 
    fa[ch[x][0]] = fa[ch[x][1]] = 0;
    x = merge(ch[x][0], ch[x][1]);  
    return;
}
int n, m; 
int main(){
    scanf("%d", &n);
    for(int i = 1; i <=n; i++){
        scanf("%d", &val[i]);
        root = merge(root, i);
    }
    cout << val[root];
    remove(2); 
    rmvroot(root); 
    cout << val[root];
}