简述
左偏树与二叉堆一样，是一种优先队列的实现。但是与二叉堆不一样，他不是一种完全二叉树，而是一种不平衡二叉树，这样做的目的是为了实现一个重要的性质--合并。通常的二叉堆并不能方便的实现两个堆之间的合并，而左偏树，却恰恰适合解决这样的问题。
实现功能
实现一个最小优先队列，是的插入、删除、合并等操作均在O(logN)的时间复杂度内完成。
实现思路
左偏树定义了一种节点叫“外节点”，即这个节点的左子树或者右子树为空。并且定义了一个性质叫“距离”，就是这个节点到他子孙中最近的外节点的距离，如果本身就是外节点，那么距离就是0，为了方便，我们把空节点的距离定义为-1。一个合法的左偏树需要满足对于任意节点，他的左子孙的距离不小于右子孙的距离，即”左偏性质“。当然，他还得有堆性质，即父亲节点的值不能大于子孙节点的值，这样才能保证优先队列的性质。同时，他还具有递归的性质，即左偏树的任意一棵子树也是左偏树。
为什么这样的结构就能实现快速合并呢？这就牵涉到我们”合并“的方法了。
当我们要合并两个左偏树的时候，我们将堆顶元素较大的那棵树与另外一棵树的右子树合并得到新树（维护堆性质），并将新树作为之前那棵树的右子树得到，如果这时右子树的距离大于左子树的距离，那么就要交换这两棵子树并将堆顶的距离重新设置（维护左偏的性质）。这是一个递归的过程，递归的终点就是合并到空节点。
由左偏树的性质可以知道，他的右子树的距离不会大于O(logN)，所以合并的复杂度也不会大于O(logN)。这就满足了快速合并的要求。
基本模版
代码语言：javascript复制#include<algorithm>
using namespace std;
const int MAXN = 100000;
struct LeftlistTree{
int n, //保存节点的个数
v[MAXN], //保存节点的值
l[MAXN], //保存左儿子的位置
r[MAXN], //保存右儿子的位置
d[MAXN]; //保存节点的距离
int merge(int x, int y);//将节点x和y的树合并
int init(int x); //新建一个单节点的子树，并返回他的堆顶元素的位置
int insert(int x, int value);//将权值为value的节点加入编号为x的左偏树中，返回新的堆顶编号
int top(int x); //获得堆顶元素，返回权值
int pop(int x); //将编号为x的树的堆顶删除
};
int LeftlistTree::merge(int x, int y){
if (!x)
return y;
if (!y)
return x;
if (v[x] < v[y])
swap(x, y);
r[x] = merge(r[x], y);
if (d[l[x]] < d[r[x]])
swap(l[x], r[x]);
d[x] = d[r[x]] 1;
return x;
}
int LeftlistTree::init(int x){
n ;
v[n] = x;
l[n] = r[n] = d[n] = 0;
return n;
}
int LeftlistTree::insert(int x, int value){
return merge(x, init(value));
}
int LeftlistTree::top(int x){
return v[x];
}
int LeftlistTree::pop(int x){
return merge(l[x], r[x]);
}
