常用二叉可并堆——左偏树

要求：了解什么是左偏树。不必熟练掌握左偏树的写法。 ## 一、左偏树的结构与性质 左偏树也是一棵二叉树，也满足堆的性质。以小根堆为例，每个非根结点的值都比它父亲大。因此在整棵左偏树中，根的值最小。 即左偏树的性质一（以小根堆为例）： $$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$$ ## 二、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; } ``` ## 三、pop 参考斜堆。 ## 四、时间复杂度分析 左偏树的左偏性保证了它不会退化成链，保证了它最坏情况下的效率。由于两棵被合并的左偏树a和b的根节点距离分别不大于$\log^{size_a+1}_2-1$和$\log^{size_b+1}_2-1$，合并的复杂度为$\log^{n^2}_2$。 然而可以从~~我写的很丑的~~代码看出，左偏树的常数并不小，在实际应用中，面对随机数据，反而比斜堆要慢。 ## 五、例题 [P3377 【模板】左偏树（可并堆）](https://www.luogu.org/problemnew/show/P3377) [P3261 JLOI2015 城池攻占](https://www.luogu.org/problemnew/show/P3261)