左偏树
<pre><code class="language-cpp">#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];
}</code></pre>