问题标题: 左偏树

今天学习了左偏树，这是一个好理解而且好写的数据结构，和二叉堆一样可以在O（1）时间内取出优先级最高的值，O（logn）时间内删除优先级最高的值，不同的是如果要合并两个堆那么二叉堆就只能跪了。而左偏树能在O（logn）的时间内实现两个堆的合并。

左偏树有两个重要的性质，

1、树中每个元素小于或大于其父亲节点的值（堆性质）

2、定义节点的距离为当前节点向下到叶子节点最少所需的边数，叶子节点的距离为0,空节点的距离是-1，令dist[i]表示i节点的距离，那么dist[i]=dist[right[i]]+1;dist[left[i]]>=dist[right[i]]，所以左偏树的左右子树都是左偏树。

如下图就是一颗左偏树

左偏树最核心操作就是【合并】。删除最大，插入都可由合并得到

假如我们要构造最小堆

Merge(A,B)表示合并A和B

假如A或B中的一个为空返回另一棵树即可

否则，若A根节点小于B的根节点（否则把A和B交换），把A的根作为新的树的根然后Merge(right(A),B)即可

由于Merge过程中性质（2）可能被破坏，那么把左子树和右子树交换重新计算dist即可

C++ Code：

[cpp] view plain copy

1. Lheap* merge(Lheap* a,Lheap *b){  
2.     if(a==NULL)return b;  
3.     if(b==NULL)return a;  
4.     if(b->val>a->val)swap(a,b);  
5.     a->r=merge(a->r,b);  
6.     if(dis(a->l)<dis(a->r))swap(a->l,a->r);  
7.     a->dis=dis(a->r)+1;  
8.     return a;  
9. }  

插入操作很简单，把插入的点看做看做一个左偏树，直接Merge即可

删除最小也很简单，先Merge(left(A),right(A)),再删除原来的根就行

查询即为根节点的值

——————————————————————————————————————————————————————————————————————————
题目：HDOJ 1512 Monkey King

题目大意：有N个数字，初始情况，每个数字单独构成一个集合，每次把X，Y所在集合的最大值除以2，然后合并X和Y所在集合，询问新集合的最大值，若XY本身就在同一集合输出-1

做法：并查集+左偏树维护即可

Code C++:

Accepted15121046MS16180K1627 BG++

[cpp] view plain copy

1. #include <cstdio>  
2. #include <cstring>  
3. #include <cstdlib>  
4. #include <algorithm>  
5. #define MAXN 100001  
6. using namespace std;  
7. struct Lheap{  
8.     int val,dis;  
9.     Lheap *l,*r;  
10. };  
11. Lheap* tree[MAXN];  
12. int fa[MAXN];  
13. void init(Lheap* &t,int val){  
14.     t=new Lheap;  
15.     t->val=val;  
16.     t->l=t->r=NULL;  
17.     t->dis=0;  
18. }  
19. int findset(int x)  
20. {  
21.     int y,root,t;  
22.     y=x;  
23.     while(y!=fa[y])y=fa[y];  
24.     root=y;  
25.     y=x;  
26.     while(fa[y]!=y){  
27.         t=fa[y];  
28.         fa[y]=root;  
29.         y=t;  
30.     }  
31.     return root;  
32. }  
33. int Union(int x,int y){  
34.     int fx=findset(x);  
35.     int fy=findset(y);  
36.     if(fx==fy)return -1;  
37.     fa[fx]=fy;  
38.     return fy;  
39. }  
40. int dis(Lheap *a){return (a)?(a->dis):(-1);}  
41. Lheap* merge(Lheap* a,Lheap *b){  
42.     if(a==NULL)return b;  
43.     if(b==NULL)return a;  
44.     if(b->val>a->val)swap(a,b);  
45.     a->r=merge(a->r,b);  
46.     if(dis(a->l)<dis(a->r))swap(a->l,a->r);  
47.     a->dis=dis(a->r)+1;  
48.     return a;  
49. }  
50. Lheap* delmax(Lheap *a){  
51.     if(!a)return NULL;  
52.     return merge(a->l,a->r);  
53. }  
54. int solve(int fx,int fy){  
55.     Lheap *t1,*t2,*t3,*t4;  
56.     init(t1,tree[fx]->val/2);  
57.     t3=delmax(tree[fx]);  
58.     t3=merge(t1,t3);  
59.     init(t2,tree[fy]->val/2);  
60.     t4=delmax(tree[fy]);  
61.     t4=merge(t2,t4);  
62.     fy=Union(fx,fy);  
63.     tree[fy]=merge(t3,t4);  
64.     return tree[fy]->val;  
65. }  
66. int main()  
67. {  
68.     //freopen("gen.out","r",stdin);  
69.     int n;  
70.     while(scanf("%d",&n)!=EOF){  
71.         for(int i=1;i<=n;i++){  
72.             int atk;  
73.             scanf("%d",&atk);  
74.             fa[i]=i;  
75.             init(tree[i],atk);  
76.         }  
77.         int que;  
78.         scanf("%d",&que);  
79.         while(que--){  
80.             int x,y;  
81.             scanf("%d%d",&x,&y);  
82.             int fx=findset(x),fy=findset(y);  
83.             if(fx!=fy)printf("%d\n",solve(fx,fy));  
84.             else printf("-1\n");  
85.         }  
86.         for(int i=1;i<=n;i++)delete tree[i];  
87.     }  
88.     return 0;  
89. }