通常我们使用的二叉堆，是用一个数组实现的完全二叉树，对于查询有O(1)复杂度，对于插入、删除有O(logn)复杂度
而且常数比较小，是一个比较优秀的数据结构
但是。
当我们需要合并两个堆的时候，用普通的二叉堆就显得吃力了，时间复杂度达到O(mlogn)
这个时候可并堆这种数据结构就出现了。而在其中，尤以左偏树代码复杂度和时间复杂度综合得比较优秀
左偏树
在介绍左偏树之前，得先引入一个叫距离(d)的概念：
在左偏树中，一个节点u的距离，等于u到它和叶子节点中最近的左右儿子不满的节点【也就是可插入的节点】的距离。
然后左偏树是这样定义的：
左偏树是左儿子距离不小于右儿子距离的二叉堆。
这样子有什么用呢？
当插入节点时，只需往右儿子插入，可降低插入的时间复杂度。
实现
首先每个节点这样声明：
struct LT{
int v,l,r,d;
LT() {l=r=d=0;}
}e[maxn];
左偏树的所有操作都是以合并操作为基础的：
对于根节点为u和v两个左偏树是这样合并的：
1、如果其中有空节点，直接返回另一个非空结点
2、选择节点值较小的作为根节点，然后合并根节点的右儿子和另一个节点【merge(root.r,v)】【递归】
3、维护根节点的距离。我们设空节点的距离为-1，那么根节点的距离=右儿子距离+1
C++代码：
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(e[b].v<e[a].v) a^=b^=a^=b;
e[a].r=merge(e[a].r,b);
if(e[e[a].l].d<e[e[a].r].d) swap(e[a].l,e[a].r);
if(!e[a].r) e[a].d=0;
else e[a].d=e[e[a].r].d+1;
return a;
}
有了merge操作其他一切操作就都特别简单了：
insert操作：先将建立一个新节点，再将新节点看做一棵树与原树合并。
del操作：合并根节点的左右子树
void insert(int x){
int b=++siz;
e[b].v=x;
if(!rt) rt=b;
else rt=merge(rt,b);
}
void del(){rt=merge(e[rt].l,e[rt].r);}
左偏树其实甚至可以当普通的二叉堆使用，只不过常数大一些，由于编程难度不高，但有时用的甚至可以成为替代二叉堆的一个选择。
洛谷PP3377【模板】可并堆（左偏树）
一道板题
但用了左偏树+并查集
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005,INF=2000000000;
inline int read(){
int out=0,flag=1;char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
return out*flag;
}
int N,M;
struct LT{
int v,l,r,d,f;
LT() {l=r=d=f=0;}
}e[maxn];
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(e[a].v>e[b].v||(e[a].v==e[b].v&&a>b)) swap(a,b);
e[a].r=merge(e[a].r,b);
e[e[a].r].f=a;
if(e[e[a].l].d<e[e[a].r].d) swap(e[a].l,e[a].r);
e[a].d=e[e[a].r].d+1;
return a;
}
void del(int r){
e[e[r].l].f=e[e[r].r].f=0;
merge(e[r].l,e[r].r);
e[r].v=-1;
}
int find(int u){
if(!e[u].v==-1) return 0;
while(e[u].f) u=e[u].f;
return u;
}
int main()
{
e[0].d=-1;
N=read();
M=read();
for(int i=1;i<=N;i++)
e[i].v=read();
int cmd,a,b,fa,fb;
while(M--){
cmd=read();
if(cmd&1){
a=read();
b=read();
if(e[a].v==-1||e[b].v==-1) continue;
fa=find(a);
fb=find(b);
if(fa!=fb) merge(fa,fb);
}else{
a=read();
if(e[a].v==-1) printf("-1
");
else{
fa=find(a);
printf("%d
",e[fa].v);
del(fa);
}
}
}
return 0;
}
洛谷P1456 Monkey King
差不多的题，左偏树+并查集
【猴子找朋友来帮忙自己却不打= =】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005,INF=2000000000;
inline int read(){
int out=0,flag=1;char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
return out*flag;
}
int N,M;
struct LT{
int v,l,r,d;
LT() {l=r=d=0;}
}e[maxn];
int fa[maxn];
int find(int x){return fa[x]==x ? x:fa[x]=find(fa[x]);}
int merge(int u,int v){
if(!u) return v;
if(!v) return u;
if(e[u].v<e[v].v) u^=v^=u^=v;
e[u].r=merge(e[u].r,v);
fa[e[u].r]=u;
if(e[e[u].l].d<e[e[u].r].d) swap(e[u].l,e[u].r);
e[u].d=e[e[u].r].d+1;
return u;
}
int del(int u){
int lc=e[u].l,lr=e[u].r;
e[u].l=e[u].r=0;
fa[lc]=lc;fa[lr]=lr;
return merge(lc,lr);
}
int main()
{
e[0].d=-1;
int a,b,Fa,Fb;
while(cin>>N){
for(int i=1;i<=N;i++) {e[i].v=read();e[i].l=e[i].r=e[i].d=0;fa[i]=i;}
M=read();
while(M--){
a=read();
b=read();
Fa=find(a);
Fb=find(b);
if(Fa!=Fb){
a=del(Fa);
b=del(Fb);
e[Fa].v>>=1;
e[Fb].v>>=1;
a=merge(a,Fa);
b=merge(b,Fb);
a=merge(a,b);
printf("%d
",e[a].v);
}else printf("-1
");
}
}
return 0;
}
洛谷 P1552 [APIO2012]派遣
这是一道左偏树+树上DP
用大根堆维护，将所有的儿子【包括儿子的子树】建立成堆，删去最大的直至工资在预期范围内，就可以得到以该点为管理者的最大收益。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn=100005,INF=2000000000;
inline int read(){
int out=0,flag=1;char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
return out*flag;
}
int N,M,lson[maxn],rb[maxn],root;
LL dp[maxn],lead[maxn];
struct LT{
LL v;
int l,r,d;
LT() {l=r=d=0;}
}e[maxn];
struct node{
LL v;
int cnt,rt;
};
int merge(int u,int v){
if(!u) return v;
if(!v) return u;
if(e[u].v<e[v].v) u^=v^=u^=v;
e[u].r=merge(e[u].r,v);
if(e[e[u].l].d<e[e[u].r].d) swap(e[u].l,e[u].r);
e[u].d=e[e[u].r].d+1;
return u;
}
int del(int u) {return merge(e[u].l,e[u].r);}
node dfs(int u){
if(!lson[u]){
dp[u]=e[u].v<=M ? lead[u]:0;
return e[u].v<=M ? (node){e[u].v,1,u}:(node){0,0,0};
}else{
int rt=u,cnt=1,v=lson[u];
LL s=e[u].v;
node t;
while(v){
t=dfs(v);
cnt+=t.cnt;s+=t.v;rt=merge(rt,t.rt);
v=rb[v];
}
while(s>M){
s-=e[rt].v;
rt=del(rt);
cnt--;
}
dp[u]=(LL)lead[u]*(LL)cnt;
return (node){s,cnt,rt};
}
}
int main()
{
e[0].d=-1;
int f;
N=read();
M=read();
for(int i=1;i<=N;i++){
f=read();rb[i]=lson[f];lson[f]=i;
if(!f) root=i;
e[i].v=read();
lead[i]=read();
}
dfs(root);
LL ans=0;
for(int i=1;i<=N;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}