卡不掉、常数小的可并堆——随机堆

## 一、随机堆的结构 参见斜堆。 ## 二、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; } ``` 这玩意甚至不需要交换左右儿子！ ## 三、pop 参考斜堆。 ## 四、时间复杂度分析 显然，合并操作最坏$O(n)$，均摊$O(\log n)$。常数小，代码复杂度小~~（说得好像左偏树代码复杂似的）~~，可以完全替代左偏树。 ## 五、例题 就是左偏树的例题。