左偏树

一种可以合并的堆

前置知识

dist

对于一棵二叉树，我们定义 外节点 为左儿子或右儿子为空的节点，定义一个外节点的 为 ，一个不是外节点的节点 为其到子树中最近的外节点的距离加一。空节点的dist为0。

那么左偏树就是一颗满足堆的性质的二叉树，它的左儿子的dist大于等于右儿子的

核心

核心操作是合并，合并到时候，要满足堆得性质，对于小根堆，就把较小的根作为新的根节点，然后递归合并右儿子和另外一个堆。如果不满足左偏性质，还要交换一下儿子。

插入