左偏树是一种不需要证明的可并堆(呸)

建树O(NlgN) - O(N)

合并O(lgN)

删除O(1)

刚开始每个结点都是一个左偏树，每个结点有四个属性

Left[i], Right[i], Key[i], Dist[i]

Left[i], Right[i]代表左右儿子

左右儿子有一个空的则该结点为外结点

Dist[i]定义为i到i的后代的外结点中距离最小的

维护极小值的左偏树始终满足性质 Key[i] >= Key[f[i]], Dist[Left[i]] >= Dist[Right[i]]

由于这个性质，显然若i是外结点Dist[i] = 0 否则 Dist[i] = Dist[right[i]] + 1(如果我们把Dist[0]=-1则可直接进行后者操作)

合并：

合并操作非常容易理解，在合并两个左偏树a,b的时候，如果Key[a] < Key[b]，那么只需要对Right[a]与b合并，合并后的结果作为新的Right[a]去更新a

Procedure Merge(a, b)

if Key[a] > Key[b] -> Swap(a, b)

Right[a] = Merge(Right[a], b)

if Dist[Left[a]] < Dist[Right[a]] -> Swap(Left[a], Right[a])

Dist[a] = Dist[Right[a]] + 1

End Procedure

删除:

删除结点时，只需要将该结点的左右儿子合并，然后替换这个点，再维护一下该点祖先的左偏性即可。

建树:

建树既可以不断地插入结点，也可以用两两合并的循环队列的方式合并，虽然理论复杂度有差别，但是实际实现是由于常数问题导致其复杂度差不多(当我没说)