Skip to content

Latest commit

 

History

History
26 lines (17 loc) · 1.27 KB

leftist.md

File metadata and controls

26 lines (17 loc) · 1.27 KB

堆合并:左偏树

最小堆/最大堆如果两个堆进行合并,时间复杂度较高,左偏树是可合并的二叉堆,首先满足所有的堆的性质,其外,各种操作时间复杂度都是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的距离。

左偏树合并操作合并的是两棵左偏树,对于堆的插入,就是合并一棵树和一个节点,对于堆的删除,就是合并根的两棵子树。

努力写作中...