RainAir
My OI Blog
RainAir
左偏树学习笔记

定义

大家都知道优先队列吧。
有时候我们需要合并优先队列,反正我们不能重新插入吧,我们就需要一种神奇的数据结构–可并堆

可并堆可以支持在$O(NlogN)$下进行插入,删除,合并,求极值。
在OI选手中,实现可并堆的最好方法是左偏树
那么左偏树是递归定义的,它与二叉堆不同,他不是一棵完全二叉树。
左偏树中的重要定义是NPL-表示该结点到最近的外部结点的位置。
满足要求 堆的要求+做结点的NPL一定不小于有结点的NPL
得到$ NPL(i) = NPL(i.right) + 1 $ $ max{NPL} < log(N+1) $
现在我们可以发现,这个堆大部分时候是向左偏的,所以说保证复杂度的是它的右链,所以所有操作 都被放到右链上 。

操作

对于小根堆H1和H2的合并(小根堆)
如果$ H1==NULL $或$ H2==NULL $那就$ return H1+H2 $
对于合并后的$ H1 $,如果左右子树的$ Npl $破坏规则,直接交换左右子树
以上反之亦然
注意一下找父亲过程要路径压缩一下,不然会被卡成 $O(n)$。

代码

左偏树(可并堆)

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/139
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

左偏树学习笔记
定义 大家都知道优先队列吧。 有时候我们需要合并优先队列,反正我们不能重新插入吧,我们就需要一种神奇的数据结构--可并堆 可并堆可以支持在$O(NlogN)$下进行插入,删除,合并,求…
扫描二维码继续阅读
2018-05-19
标签
近期评论