首页 > 其他 > 详细

左偏树

时间:2020-01-22 21:23:16      阅读:82      评论:0      收藏:0      [点我收藏+]

左偏树可以用来维护可并堆(并查集加堆)

可以用并查集一样的路径压缩来优化复杂度

路径压缩后\(fa\)记录的就不为其原树中的父亲,而是用来表示堆与堆之间的关系

\(dis:\)表示该节点到它子树内最近的叶子节点的距离

节点的左儿子的距离不小于右儿子的距离,每次合并时,将一棵树合并到另一棵树的右子树,来保证复杂度

\(dis[x]=dis[rs[x]]+1\)

\(n\)个节点的左偏树距离最大为\(log(n+1)-1\)

\(merge:\)\(y\)合并在\(x\)上,返回\(x\),即为合并后树的根

\(merge\)\(del\)操作都需保证节点为其所在堆的根

\(code:\)

int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(val[x]>val[y]) swap(x,y);
    rs[x]=merge(rs[x],y),fa[rs[x]]=x;
    if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
    if(rs[x]) dis[x]=dis[rs[x]]+1;
    else dis[x]=0;
    return x;
}
void del(int x)
{
    val[x]=-1;
    fa[ls[x]]=ls[x],fa[rs[x]]=rs[x];
    fa[x]=merge(ls[x],rs[x]);
}

左偏树

原文:https://www.cnblogs.com/lhm-/p/12229591.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!