Mythsman


乐极生悲,苦尽甘来。


左偏树简述

简述

左偏树与二叉堆一样,是一种优先队列的实现。但是与二叉堆不一样,他不是一种完全二叉树,而是一种不平衡二叉树,这样做的目的是为了实现一个重要的性质--合并。通常的二叉堆并不能方便的实现两个堆之间的合并,而左偏树,却恰恰适合解决这样的问题。

实现功能

实现一个最小优先队列,是的插入、删除、合并等操作均在$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]);
}