左偏树与二叉堆一样,是一种优先队列的实现。但是与二叉堆不一样,他不是一种完全二叉树,而是一种不平衡二叉树,这样做的目的是为了实现一个重要的性质--合并。通常的二叉堆并不能方便的实现两个堆之间的合并,而左偏树,却恰恰适合解决这样的问题。
实现一个最小优先队列,是的插入、删除、合并等操作均在O(logN)的时间复杂度内完成。
左偏树定义了一种节点叫“外节点”,即这个节点的左子树或者右子树为空。并且定义了一个性质叫“距离”,就是这个节点到他子孙中最近的外节点的距离,如果本身就是外节点,那么距离就是0,为了方便,我们把空节点的距离定义为-1。一个合法的左偏树需要满足对于任意节点,他的左子孙的距离不小于右子孙的距离,即”左偏性质“。当然,他还得有堆性质,即父亲节点的值不能大于子孙节点的值,这样才能保证优先队列的性质。同时,他还具有递归的性质,即左偏树的任意一棵子树也是左偏树。
为什么这样的结构就能实现快速合并呢?这就牵涉到我们”合并“的方法了。
当我们要合并两个左偏树的时候,我们将堆顶元素较大的那棵树与另外一棵树的右子树合并得到新树(维护堆性质),并将新树作为之前那棵树的右子树得到,如果这时右子树的距离大于左子树的距离,那么就要交换这两棵子树并将堆顶的距离重新设置(维护左偏的性质)。这是一个递归的过程,递归的终点就是合并到空节点。
由左偏树的性质可以知道,他的右子树的距离不会大于O(logN),所以合并的复杂度也不会大于O(logN)。这就满足了快速合并的要求。
#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]);
}