可并堆

简介

一般的堆支持

1. 求最值
2. 删除最值
3. 插入任意值

假设再加入一个操作，合并两个堆，就需要用可并堆来实现。

左偏树

性质

1. 节点的键值小于或等于它的左右子节点的键值。
2. 节点的左子节点的距离不小于右子节点的距离。
3. 节点的距离等于它的右子节点的距离加1。
4. 一棵N个节点的左偏树root节点的距离最多为log(N+1)-1。

其他操作

增加一个节点：将原树和只有一个节点的树合并。
删除根节点：合并根节点的左右子树。

随机合并

左偏树记录的信息比较复杂，一个简单替代方案是随机合并，
这样因为树的期望高度不大，效率也很高。

启发式合并

每次把较小的集合中每个元素，依次删除，并加入到较大的集合中。

参考题目

Luogu P1552
注意到对于每个人，薪水总预算相同，所以可以用可并堆，如果超过预算删去最贵的人。

Luogu P3377
左偏树模板题。

Luogu P4331
论文题，也可以用堆做。

参考资料

https://blog.csdn.net/chenjiayi_yun/article/details/38347117