最小堆/最大堆如果两个堆进行合并，时间复杂度较高，左偏树是可合并的二叉堆，首先满足所有的堆的性质，其外，各种操作时间复杂度都是O(logN)。
左偏树的树节点需要保存的信息有：
1.左右子树节点编号
2.此节点到有空子结点的最短距离len(空子节点的节点，就是子节点数不足2个的节点)
3.自身权值
左偏就是每个节点的左子节点的len不小于右子节点的len（但并不代表左子节点数一定不小于右子节点数），那么可知左偏树中一个节点的距离就是右儿子距离+1（或没有右儿子），且左右子树都是左偏树。
合并树A和树B的操作方法如下：
1.如果A或B有一个是空树，返回另一个。
2.如果A的优先级比B低，交换A,B。(确保左堆根节点小于右堆根节点)
3.递归处理，将B和A的右子树合并。(B,Right(A)递归处理)
4.如果合并过后A的右儿子距离大于A的左儿子，交换A的左右儿子。(确保左儿子距离大于右儿子)
5.更新A的距离。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
左偏树合并操作合并的是两棵左偏树，对于堆的插入，就是合并一棵树和一个节点，对于堆的删除，就是合并根的两棵子树。
赞赏支持
如果你觉得文章不错，请打个赏吧！
