斜堆学习笔记+复杂度证明

和左偏树几乎一模一样，唯一的区别是左偏树合并后判断如果左儿子深度小于右儿子则交换左右儿子，而斜堆直接无脑交换。

复杂度是均摊的 $O(n\log n)$

证明：

定义重结点为右儿子大小大于左儿子的结点，否则为轻结点。

定义右路径为一直往右走的路径，包不包含自己不重要。

定义势能 $\Phi$ 为所有结点右路径上的重结点的个数之和。显然初始势能为 $0$，最终势能非负。

考虑一次合并的两个点 $u,v$，设它们右路径上轻、重点个数分别为 $l_u,h_u,l_v,h_v$

那么这次合并的实际代价为 $l_u+h_u+l_v+h_v$

而在右路径上，一个重结点右儿子本来就比左儿子重，合并又发生在右儿子，交换后左儿子大于右儿子，所以合并后重结点一定会变轻结点。

考虑最坏情况，所有轻结点都变成重结点，势能增加量 $\Delta \Phi =l_u+l_v-h_u-h_v$

均摊后的代价为实际代价+势能增加量，即 $2(l_u+l_v)$

显然右路径的轻结点个数为 $\log$ 级别的，所以总复杂度为 $O(n\log n)$

所以整棵树的深度还是没保证……

总结

以上是生活随笔为你收集整理的斜堆学习笔记+复杂度证明的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。