基本概念
左偏树是一种易实现的可合并堆，它是二叉树的变种，除了维护堆的性质以外，对于每一个节点，都将维护一个(s)值（表示这个点距离最近叶子节点的距离（这里的叶子节点包含只含有一个儿子的节点）。左偏树需要保证每个节点的右儿子节点的(s)值小于等于做儿子节点的(s)值。相较于二叉堆，左偏树的结构往往是很不平衡的。
性质
- 左偏树根节点的(s)值不超过(log(|V|))
- 左偏树是可并的
- 如果规定空节点的(s)值为(-1)，那么每个点的(s)值等于其右儿子的(s)值(+1)
算法
合并操作
采用递归的方式合并两个左偏树
- 如果有一棵树为空，返回另一颗树
- 将根节点键值较小的树与较大树的右儿子合并
- 如果合并后违反了左偏性质，交换两个儿子，更新当前节点的(s)值
插入
视为一颗只有一个元素的左偏树合并
删除根操作
删除根，合并左右两颗子树
复杂度
因为不断和右子树进行合并，根的(s)值不超过(log(|V|))，所以复杂度是(log(|V|))
代码实现
接口
int Init(int x)
输入： x 单点左偏树的权值
输出：新建的左偏树的编号
int Insert(int x, int y)
复杂度：(log(n))
输入： x, y 向编号为x的左偏树中插入一个权值为y的节点
输出：新的堆顶的编号
int Top(int x)
复杂度： (1)
输入： x 左偏树的编号
输出： 编号为x的左偏树的堆顶的权值
int Pop(int x)
复杂度： (log(n))
输入： x 左偏树的编号
输出： 删除编号为x的左偏树的堆顶，返回新的堆顶编号
int Merge(int x, int y)
复杂度： (log(n))
输入： x, y 两颗要合并的左偏树的编号
输出： 新的堆顶编号
代码
int tot, v[maxn], l[maxn], r[maxn], d[maxn];
int Merge(int x, int y) { // return new lefttree
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 Init(int x) {
tot ++;
v[tot] = x;
l[tot] = t[tot] = d[tot] = 0;
}
int Insert(int x, int y) {
return (Merge(x, Init(y)));
}
int Top(int x) {
return (v[x]);
}
int Pop(int x) {
return (Merge(l[x], r[x]));
}