(可并堆)p3377 左偏树

左偏树是一种支持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,没了

上一篇:git 本地仓库版本无法从远程更新到本地


下一篇:AcWing 787. 归并排序