左偏堆学习

发表于 | 分类于 | 评论数： | 阅读次数：

简单说两句

这其实是一个简单易懂的可合并堆。

正文

概念

可合并堆：可以合并的堆（字面意思）

左偏树之前有一个“距离”要说：从x这个点出发，到叶子节点所经过的边数

左偏堆：又称左偏树（废话）

  1. 它有堆的性质（这个不知道自己百度或看书）。
  2. x的左儿子的“距离”比右儿子大或等于。

简单解答

那这左偏堆搞的那么奇怪干什么？

首先，要想合并两个堆，用暴力的方法一定会超慢，而左偏树就可以将合并做到log2(n)的级别！！

那它为什么是log2(n)呢？

简单的说就是利用了它的性质，之后给出详细的合并方法，请自己想这和性质有何关系。

合并操作

现在，我们要合并根为x的小堆和根为y的小堆。

merge(x,y)函数是指合并上述两个堆所组成的新堆的根，x经过一系列操作后变为新堆的根。

如果现在有一个堆是空堆，那就直接返回不为空的那个堆。

1
if(!x||!y) return x+y;

接下来就要用维护堆的方式来合并了。

如果当前x点的权值大于y点的权值，就交换x和y（如果权值相等，可以按秩合并）,此时x就是新根了。

结束后还要继续合并x的右节点和y。再维护左偏堆的性质。(根的“距离”=右儿子的“距离”+1)

就这样结束了！！！

合并代码

下面给出merge代码：

  1. fa[x]:x的父节点。

  2. ls[x],rs[x]:x的左右儿子。

  3. dis[x]:x的“距离”。
1
2
3
4
5
6
7
8
9
int merge(int x,int y){
	if(!x||!y) return x+y;
	if(a[x]>a[y]||(a[x]==a[y]&&x>y)) swap(x,y);//找新根和按秩合并
	rs[x]=merge(rs[x],y);//向下合并
	if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);//维护性质
	fa[ls[x]]=fa[rs[x]]=fa[x]=x; dis[x]=dis[rs[x]]+1;//更新几个重要信息
	return x;
}
//有细心的人看出了fa[]好像没用？现在没用而已，之后肯定有用的！！！

找根

如何找一点所在堆的堆顶（也就是根）？

用并查集来实现！！！（fa[]有用了吧）

但我有一个问题没搞懂，并查集维护的话要不要路径压缩？？？

问了好多大佬，有的说可以压，不然复杂度会降低。但又有的说会破坏性质，不能压！！

经过我的实测，好像真的没问题，那就压吧！！（不然TLE缠绕在你身边）

代码：

1
太简单不写了，如果真的不会可以看例题中的。（不是我懒）

删除根节点

怎么删除一个堆的根呢?

很简单，先将这个点的权值赋值为-1，再将它的左右儿子合并就好了。

代码：（知道有点看不懂，但有代码了一定可以自己钻研出来的）

1
2
3
4
5
void pop(int x){
    a[x]=-1;
    fa[ls[x]]=ls[x],fa[rs[x]]=rs[x];
    fa[x]=merge(ls[x],rs[x]);
}

结束

好像就这么几个我会的，如果之后还学到了的话继续更（如果还记得。

完美撒花！！！！！！

例题

之后随机更新：

  1. …