既然新学了左偏树, 那我就来写一些学了左偏树之后的总结吧
Part 1 左偏树是干嘛的
首先, 它支持的是两个堆的合并过程那么最容易想到的是把一个堆的元素全部弹出, 一个一个加入另一个堆中, 就合并了显然这样合并的复杂度是 O(n) 的, 再加上程序的其他部分, 很慢我们就考虑让复杂度减小到 O(logn), 很恐怖, 没错, 这就是左偏树存在的意义
那为什么要叫左偏树, 顾名思义, 往左偏的树, 我们首先命名一个 dis[],ls[],rs[], 表示一个节点到他下方最近的空节点的距离, 左孩子, 右孩子显然, 为了维护左偏那么 dis[ls[i]] 一定要维护大于 dis[ys[i]], 如果小于了, 就换并且为了保证这个点的 dis 是离空节点最近的, 显然是维护 dis[i]=dis[rs[i]]+1 至于为什么一定要左偏, 是因为我们之后的操作是往右合并, 所以操作次数会减少 (具体看后文把)
Part 2 实现过程 (以大根堆为例, 小根堆类推)
. 合并过程
我们来模拟一下, 如果两个堆 A,B 要合并, 那么新的堆顶元素一定是两个堆堆顶元素的最大值这是必然的, 那么我们在比较完之后, 把两个堆顶的最大值放在 A 堆的堆顶, 再把小的那一个放在 B 堆的堆顶, 此时 A 堆的堆顶已经对后面的合并没有影响了, 就可以继续合并更小的值了, 我们考虑把 B 堆往 A 堆的右孩子决定 ( 需要注意: 我们在整个左偏树合并过程中, 都直接以堆顶的编号作为堆的序号, 所以到了右孩子, 就相当于到了以右孩子为堆顶的一个堆), 这样不就是一个递归嘛, 不停地比较, 然后合并新堆和右孩子
- int Merge(rg int A,rg int B)// 合并 A 堆和 B 堆
- {
- if(!A||!B)return A+B;// 如果有一个堆空了 (堆顶元素编号为 0), 就返回另一个堆顶
- if(key[A]<key[B])swap(A,B);// 维护大根堆
- rs[A]=Merge(rs[A],B);// 新的 A 的右孩子是 A 的右孩子和新 B 合并的结果
- if(dis[ls[A]]<dis[rs[A]])swap(ls[A],rs[A]);// 维护左偏
- dis[A]=dis[rs[A]]+1;// 维护当前节点的 dis 值
- return A;// 返回堆顶元素
- }
. 删除过程
很容易想到, 删除堆顶元素, 不就是把堆顶元素的左孩子和右孩子合并嘛
- int Delete(rg int A)// 删除 A 堆的堆顶元素
- {
- return Merge(ls[A],rs[A]);// 合并 A 的左孩子和右孩子, 并返回堆顶
- }
来源: http://www.bubuko.com/infodetail-2537466.html