左偏树是一种支持log(n)合并的堆式数据结构。
定义:
外节点:不同时拥有左右儿子的节点
x的距离(dist):x到达子树中(包括自己)最近的外节点的距离,特别定义空节点的dist为-1
基本性质和结论:
除了满足堆的每个节点都 大于 或者 小于 左右儿子的性质,还满足(大概不全)
1、左偏性:对于每个节点, dist[ls]>=dist[rs], ls=leftson rs=rightson
2、dist[x] = dist[rs] + 1
3、n个节点的左偏树的dist[root] = log_2(n)
基本操作merge(注:以下均为小根堆)
总的来说,merge总节点数不变,但需要同时维护堆的性质和左偏性。可以通过不断递归以权值为标准把堆分成很多单元,再向上合并,最后再维护左偏性。
流程:
1、对于两个左偏树的根节点x, y,v[x] < v[y]
2、用以rs[x]为根的左偏树去和以y为根的左偏树merge(向下递归相当于把两个左偏树拆成很多片),再让rs[x] = 合并后的结果
3、重复以上12操作,如果!x||!y为空节点直接返回 x+y(每次都是y不变,x = rs[x],到最后“rs[x] = merge(rs[x], y);”中rs[x]是0、y不是0,然后把y放在rs[x]上)
4、维护左偏性:如果dist[rs[x]] > dist[ls[x]],则swap(rs[x], ls[x]);
int v[maxn], ls[maxn], rs[maxn], dist[maxn];
int merge(int x, int y)
{
if (!x || !y)return x + y;
if (v[x] > v[y])swap(x, y);//ensure v[x]<v[y]
rs[x] = merge(rs[x], y);
if (dist[rs[x]] > dist[ls[x]])swap(rs[x], ls[x]);
dist[x] = dist[rs[x]] + 1;
return x;
}
插入合并都是用merge,没了