最简单的二叉可并堆——斜堆

要求：了解什么是可并堆，什么是斜堆。不必熟练掌握斜堆的写法。 ## 一、什么是可并堆 一般的二叉堆支持在$\log n$时间内完成以下操作： 1. 插入一个值 2. 获得或取出最小值（或最大值）。 这样的二叉堆想必大家早已经能熟练地用```std::priority_queue```水过了。 可并堆还要求在$\log n$的时间内完成两个堆的合并。原来的二叉堆要想完成这一操作，时间复杂度为$n\log n$，使用启发式合并的话，比我们想要的复杂度足足多了一个$\log$，这是不清真的。 为了实现这一操作，我们可以使用斜堆、左偏树、随机堆或配对堆~~再或者pb_ds中的各种优先队列~~。 ## 二、斜堆的整体结构 斜堆是一棵二叉树，满足堆的性质。以小根堆为例，每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。 原来我们写过的二叉堆是一棵完全二叉树，但斜堆不是。斜堆甚至不必保证平衡，每个结点的左右儿子的大小关系也没有任何规定。 对于每个节点，我们这样描述： ``` struct Node { int ch[2],val; } ``` 也就是记录自己的值和左右儿子。 ## 三、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; } ``` ## 四、pop 删除根节点，合并两个子树即可。 ## 五、时间复杂度分析 最坏情况下，斜堆可以被精心构造的毒瘤数据卡成一条链，时间复杂度$O(n)$。然而，在绝大多数情况下，均摊时间复杂度是$O(\log n)$，有人证明，其均摊复杂度最坏不超过$O(4\log n)$。 同时，有这样一个问题，如果合并后的左子树仍远大于右子树，交换后再进行后续合并不就更偏了吗？ ## 六、例题 [P2475 SCOI2008 斜堆](https://www.luogu.org/problemnew/show/P2475)