左偏树

左偏堆可以完成优先队列的插入节点，出队，还有合并。

合并：

int merge(int a,int b){
    if(a==0)return b;
    if(b==0)return a;
    if(heap[a].v<heap[b].v)swap(a,b);
    heap[a].r=merge(heap[a].r,b);
    heap[heap[a].r].f=a;
    if(heap[heap[a].l].dis<heap[heap[a].r].dis)swap(heap[a].l,heap[a].r);
    if(heap[a].r==0)heap[a].dis=0;
    else heap[a].dis=heap[heap[a].r].dis+1;
    return a;
}

出队：

int pop(int a){
    int l=heap[a].l;
    int r=heap[a].r;
    heap[l].f=l;
    heap[r].f=r;
    heap[a].l=heap[a].r=heap[a].dis=0;
    return merge(l,r);
}

例题：ZOJ2334

题目大意：有n个猴子，一开始每个猴子只认识自己。每个猴子有一个力量值，力量值越大表示这个猴子打架越厉害。如果2个猴子不认识，他们就会找他们认识的猴子中力量最大的出来单挑，单挑不论输赢，单挑的2个猴子力量值减半，这2拨猴子就都认识了，不打不相识嘛。现在给m组询问，如果2只猴子相互认识，输出-1，否则他们各自找自己认识的最牛叉的猴子单挑，求挑完后这拨猴子力量最大值。

#include<cstdio>
#include<iostream>
#define N 100010
using namespace std;
int n,m;
struct node{
    int v,dis,l,r,f;
};node heap[N];
int find(int x){
    if(x==heap[x].f)return x;
    return heap[x].f=find(heap[x].f);
}
int merge(int a,int b){
    if(a==0)return b;
    if(b==0)return a;
    if(heap[a].v<heap[b].v)swap(a,b);
    heap[a].r=merge(heap[a].r,b);
    heap[heap[a].r].f=a;
    if(heap[heap[a].l].dis<heap[heap[a].r].dis)swap(heap[a].l,heap[a].r);
    if(heap[a].r==0)heap[a].dis=0;
    else heap[a].dis=heap[heap[a].r].dis+1;
    return a;
}
int pop(int a){
    int l=heap[a].l;
    int r=heap[a].r;
    heap[l].f=l;
    heap[r].f=r;
    heap[a].l=heap[a].r=heap[a].dis=0;
    return merge(l,r);
}
void work(){
    for(int i=1;i<=n;i++){
        scanf("%d",&heap[i].v);
        heap[i].dis=heap[i].l=heap[i].r=0;
        heap[i].f=i;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int a,b;scanf("%d%d",&a,&b);
        int aa=find(a),bb=find(b);
        if(aa==bb){
            printf("-1
");continue;
        }
        heap[aa].v/=2;
        int u1=pop(aa);
        u1=merge(u1,aa);
        heap[bb].v/=2;
        int u2=pop(bb);
        u2=merge(u2,bb);
        printf("%d
",heap[merge(u1,u2)].v);
    }
}
int main(){
    while(scanf("%d",&n)!=EOF){
        work();
    }
    return 0;
}

 论文链接：http://wenku.baidu.com/link?url=t55yGX-UkUdEXBhpvBwuzjKP16F7lFl0RKSVVBBW5zXWRB7rRXvLLj1jM-pzhbH834hQl0KKT4va247VmSepsGDSrYF1E3le_WpnKc2xfCi