左偏树简述

Posted on | In

简述

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

实现功能

实现一个最小优先队列，是的插入、删除、合并等操作均在$O(logN)$的时间复杂度内完成。

实现思路

左偏树定义了一种节点叫“外节点”，即这个节点的左子树或者右子树为空。并且定义了一个性质叫“距离”，就是这个节点到他子孙中最近的外节点的距离，如果本身就是外节点，那么距离就是0，为了方便，我们把空节点的距离定义为-1。一个合法的左偏树需要满足对于任意节点，他的左子孙的距离不小于右子孙的距离，即”左偏性质“。当然，他还得有堆性质，即父亲节点的值不能大于子孙节点的值，这样才能保证优先队列的性质。同时，他还具有递归的性质，即左偏树的任意一棵子树也是左偏树。

为什么这样的结构就能实现快速合并呢？这就牵涉到我们”合并“的方法了。

当我们要合并两个左偏树的时候，我们将堆顶元素较大的那棵树与另外一棵树的右子树合并得到新树（维护堆性质），并将新树作为之前那棵树的右子树得到，如果这时右子树的距离大于左子树的距离，那么就要交换这两棵子树并将堆顶的距离重新设置（维护左偏的性质）。这是一个递归的过程，递归的终点就是合并到空节点。

由左偏树的性质可以知道，他的右子树的距离不会大于$O(logN)$，所以合并的复杂度也不会大于$O(logN)$。这就满足了快速合并的要求。

基本模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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]);
}