首页 > 代码库 > 7.18晚1.5hrs

7.18晚1.5hrs

 

可并堆

左偏树中

技术分享

dist[x]=dist[rs[x]]+1

合并的时候,把权志较大的根作为根节点,把这棵树右子树和另一棵树合并。

说明白点:(上图描述有点问题)

设x表示根权值较大的左偏树,y表示根权值较小的左偏树,合并的时候把x的根节点当做新的树的根节点,把x左子树当做新的左子树,x的右子树和y合并的树作为新的右子树。最后比较dist,如果新的树的左子树的dist小于右子树的,交换。

int merge(int x,int y)//x y是要合并的左偏树的两个根 返回值是新树的根
{
    if(!x||!y)return x|y;//一个数|0还是那个数,判断空树
    if(v[x]<v[y])swap(x,y);//x是权值大的 y小
    rs[x]=merge(rs[x],y);//新的右子树是原来的右子树和y的合并树
    if(dist[rs[x]]>dist[ls[x]])swap(rs[x],ls[x]);//根据dist调整
    dist[x]=dist[rs[x]]+1;//更新x的dist的值
    return x;
}

还有...add del

int add(int x)
{
    v[++cnt]=x;//先建一个只有一个节点的树
    dist[cnt]=0;
    root=merge(cnt,root);//然后把这个数合并
}
int del()
{
    root=merge(ls[root],rs[root]);
    //合并一个节点的左儿子和右儿子,就是删除这个点啦...
}

 

7.18晚1.5hrs