几种初级二叉可并堆简介

## 前言 我问过一些男性OIer，女生的哪些习惯会让你厌恶？ 有人说：不温柔。 有人说：分块时不解均值不等式，默认块的大小为$\sqrt{n}$。 有人说：写Treap、模拟退火时用系统默认随机数种子。 有人说：利用CRT解一元模线性方程组时忽略不互质的情况直接套用公式。 还有人说：偷懒使用斜堆代替左偏树。 emm……斜堆，左偏树…… 前置知识：对[洛谷日报第11期](https://www.luogu.org/blog/henry-y/qian-xi-ji-chu-shuo-ju-jie-gou-er-cha-dui)中的二叉堆完全理解，且可以完全实现。 ## 一、可并堆 一般的二叉堆支持完成以下操作： 1. $O(\log n)$插入一个值 2. $O(1)$获得或$O(\log n)$取出最小值（或最大值）。 这样的二叉堆想必大家早已经能熟练地用```std::priority_queue```水过了。 可并堆还要求在$\log n$的时间内完成两个堆的合并。原来的二叉堆要想完成这一操作，时间复杂度为$n\log n$，使用启发式合并的话，比我们想要的复杂度足足多了一个$\log$，这是不清真的。 为了实现这一操作，我们可以使用斜堆、左偏树、随机堆、配对堆、二项堆或斐波那契堆~~再或者```pb_ds```中的各种优先队列~~。 这里讲三种容易理解，容易实现的可并堆。 ## 二、斜堆 ### 1、斜堆的整体结构 斜堆是一棵二叉树，满足堆的性质。以小根堆为例，每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。 原来我们写过的二叉堆是一棵完全二叉树，但斜堆不是。斜堆甚至不必保证平衡，每个结点的左右儿子的大小关系也没有任何规定。 对于每个节点，我们这样描述： ``` struct Node { int ch[2],val; } ``` 也就是记录自己的值和左右儿子。 ### 2、push和merge 我们可以把单独的一个节点也看成是一个斜堆，这样可以统一为```merge```操作。  一开始我们可能会想到这样的搞法：选择a和b两个斜堆中根节点键值较小的一个，让它的右子树与另一棵树递归合并下去，再把合并出的东西当做新的右子树。 但是这样下去，右子树会很dark♂，左子树却很小，斜堆变得不平衡。  我们可以再加一步操作，插入完就交换左右儿子。这样，在一次次的合并后，这个斜堆就较为平衡了。   以上操作也可以换成插入到左子树。 ``` int merge(int root1,int root2) { if(!root1||!root2) return root1+root2; if(node[root1].val>node[root2].val) std::swap(root1,root2); node[root1].ch[1]=join(node[root1].ch[1],root2); std::swap(node[root1].ch[0],node[root2].ch[1]); return root1; } ``` ### 3、pop 删除根节点，合并根节点的两个子树即可。 ### 4、时间复杂度分析 最坏情况下，斜堆可以被精心构造的毒瘤数据卡成一条链，时间复杂度$O(n)$。然而，在绝大多数情况下，均摊时间复杂度是$O(\log n)$，有人证明，其均摊复杂度最坏不超过$O(4\log n)$。 同时，有这样一个问题，如果合并后的左子树仍远大于右子树，交换后再进行后续合并不就更偏了吗？ ## 二、左偏树 ### 1、左偏树的结构与性质 左偏树也是一棵二叉树，也满足堆的性质。以小根堆为例，每个非根结点的值都比它父亲大。因此在整棵左偏树中，根的值最小。 即左偏树的性质一（以小根堆为例）： $$val_p\leq val_{lson}$$ $$val_p\leq val_{rson}$$ 左偏树的每个节点记录四个值：左儿子，右儿子，权值和高度。 ``` struct Node { int ch[2],val,height; } ``` 所谓高度，是指一个节点到其子树内最近叶节点的距离。叶节点的高度是$0$。 为了体现名字中的“左偏”，我们钦定每个节点左儿子的高度大于等于右儿子的高度。整个树就是一种左边重右边轻的状态。 即左偏树性质二： $$height_{lson}\leq height_{rson}$$ 所以，距离父节点最近的叶节点一定在右子树中，可得左偏树性质三： $$height_p=height_{rson}+1$$ 节点数一定的情况下，要使根节点的高度最大，就要让这棵树形成完全二叉树。这样可以使得离根节点最近的叶节点尽可能远。 设此时$height_{root}=k$，则有节点数$n=2^{k+1}-1$。即得所有情况下$n\geq 2^{k+1}-1$。易见左偏树性质四： $$height_{root}\leq \log^{n+1}_2-1$$ ### 2、push和merge 同样地，把```push```视为```merge```来处理。 当我们要合并两棵左偏树a和b时，不妨设$val_{roota}<val_{rootb}$。大部分操作和斜堆相同，不同的是要保证左偏性质，还要维护节点的距离。那么只需在合并后检查两个儿子的高度大小关系，当左儿子高度小于右儿子时交换即可。在返回新得到的树根前，修改根节点的高度，使其满足性质三。 合并前  合并后  ``` int merge(int root1,int root2) { if(!root1||!root2) return root1+root2; if(node[root1].val>node[root2].val) std::swap(root1,root2); node[root1].ch[1]=merge(node[root1].ch[1],root2); if(node[node[root1].ch[0]].height>node[node[root1].ch[1]].height) std::swap(node[root1].ch[0],node[root1].ch[1]); node[root1].height=node[node[root1].ch[1]].height+1; return root1; } ``` ### 3、pop 参考斜堆。 ### 4、时间复杂度分析 左偏树的左偏性保证了它不会退化成链，保证了它最坏情况下的效率。由于两棵被合并的左偏树a和b的根节点高度分别不大于$\log^{size_a+1}_2-1$和$\log^{size_b+1}_2-1$，合并的复杂度为$\log n$。 然而可以从~~我写的很丑的~~代码看出，左偏树的常数比斜堆要大，在实际应用中，面对随机数据，反而比斜堆要慢。 ## 三、随机堆 ### 1、随机堆的结构 参见斜堆。 ### 2、push和merge ```push```视为```merge```。 为了减小常数与略微减少代码量，我们必须舍弃左偏树的交换与维护。但是又不能像斜堆那样被卡成一条链。也就是说，我们要往两边都均匀插入。怎么办呢？ 随机数了解一下！ ``` int merge(int root1,int root2) { if(!root1||!root2) return root1+root2; if(node[root1].val>node[root2].val) std::swap(root1,root2); int opt=rand()&1; node[root1].ch[opt]=merge(node[root1].ch[opt],root2); return root1; } ``` 这玩意甚至不需要交换左右儿子！而且毒瘤出题人没法卡它！ ### 3、pop 参考斜堆。 ### 4、时间复杂度分析 合并操作最坏$O(n)$，均摊$O(\log n)$。常数小，代码复杂度小~~（说得好像左偏树代码复杂似的）~~，可以完全替代左偏树。 ## 四、总结 以后不需要偷懒用斜堆代替左偏树了，我们可以洗把脸然后用随机堆。~~当然```pb_ds```也是很好的选择。~~ 留三道练习题： [P3377 【模板】左偏树（可并堆）](https://www.luogu.org/problemnew/show/P3377) 这道题的并查集不能路径压缩。 [P1456 Monkey King](https://www.luogu.org/problemnew/show/P1456) 这道题是简单题。 [P3261 JLOI2015 城池攻占](https://www.luogu.org/problemnew/show/P3261) 这道题不止可并堆这一种做法，但是可并堆的代码复杂度最低。 （逃