左偏树是一种不平衡的二叉树，特点是：堆+快速的合并
每个结点包含4个元素v,d,r,l。。。。
右边的D总是比左边的D小。。。向左偏。。。。
合并操作都是向右边的子树递归的，时间复杂度低O（log(n1)+log(n2)）。
因为合并比较快。。。所以。。基本操作大都是用合并完成的。。。。。写起来非常简单。。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 const int maxn=100010; 8 int tot=0; 9 10 struct leftistheapnode 11 { 12 int v,d,r,l; 13 }heap[maxn]; 14 15 int merge(int x,int y) 16 { 17 if(!x) return y; if(!y) return x; 18 if(heap[x].v<heap[y].v) swap(x,y);///big root heap 19 heap[x].r=merge(heap[x].r,y); 20 int l=heap[x].l,r=heap[x].r; 21 if(heap[l].d<heap[r].d) swap(heap[x].l,heap[x].r); 22 if(!heap[x].r) heap[x].d=0; 23 else heap[x].d=heap[r].d+1; 24 return x; 25 } 26 27 int Init(int x) 28 { 29 tot++; 30 heap[tot].l=heap[tot].r=heap[tot].d=0; 31 heap[tot].v=x; 32 return tot; 33 } 34 35 int Insert(int x,int y) 36 { 37 return merge(x,Init(y)); 38 } 39 40 int Pop(int x) 41 { 42 return merge(heap[x].l,heap[x].r); 43 } 44 45 int Top(int x) { return heap[x].v; } 46 47 int main() 48 { 49 return 0; 50 }