左偏树和斜堆

左倾堆 / 左偏树¶

堆：完全二叉树，所有叶子都集中在左边，除了叶子其他都满秩

最小堆：每个节点都小于任意一个儿子

本节课全部用最小堆举例讲解

左倾堆的 target：加速堆的合并操作，变成 \(O(\log N)\)。

直接用普通堆合并相当于做了 N 次插入 \(O(\log N)\)

左偏树：通过自己的不平衡达到平衡

概念¶

内部节点：有两个儿子

外部节点：有 0或1 个节点

NPL （null path length） ：从某个节点到达外部节点最少经过的节点数

左偏树：树中每一个节点往左走的 NPL 不小于往右走的 NPL

计算方法：从叶子开始，爸爸的 NPL 等于俩儿子之间最小的 + 1

检查外部节点！

• 节点的儿子是外部节点，往这个儿子走的 NPL 是 0

• 结点的某个方向没有儿子，即它是外部节点，这个结点往没儿子那边走的 NPL 是 -1

左偏树右路径如果有 r 个结点，那么至少有 \(2^r - 1\) 个结点

合并¶

右路径结点数量有限制，于是全合并在右路径

递归版本¶

先思考根是谁

算法代码理解：先比较哪个堆的根节点小（记为 H1），H1 的根作为合并之后堆的根，H2 往 H1 的右子树插，也就变成了 H2 与 H1 的右子树合并（这时原来 H1 的右子树的根就变成了新的根），这就是一次递归，再进行比较，等等等。终止条件就是，有一个堆为 NULL，则直接返回另一个堆，下一步操作就是将另一个堆接在那个 NULL 的地方

if ( H1 == NULL )   return H2;  
if ( H2 == NULL )   return H1;

这两句实际是递归的终止条件：return 另一个的意思就是退出，退出到上一层，上一层干的事情是：H1->Right = Merge( H1->Right, H2 );，也就是接在右边

记得更新 NPL

递归次数：最多走右路径长度（\(\log N\)）次，因为每次都在将右子树和另一个比较

非递归版本¶

观察到：每次就是比较右路径上的结点，那么把堆的一个节点和他的左子树看成一体，那个节点的右子树看成一体，递归下去看成几块，将这些进行排序，类似于将两个有序链表合并成一个新的有序链表

最后检查从根的右路径上的结点，如果有必要就交换左子树和右子树

DeleteMin¶

等价于：删除根 + 合并两个子树

斜堆¶

左偏树和斜堆的关系 与 AVL树和splay树的关系一样

斜堆能保证 M 次操作，时间复杂度是 \(O(M \log N)\)

合并之前直接将左子树放到右边，把合并上去的放在左边

最大的最后合并进来的不用交换左右儿子，因为他没有右儿子

均摊分析¶

势能分析：

势能函数：重节点的数量

重节点：右子树的节点数量严格大于左子树结点

势能函数一般要有增增减减

规律：

• 在右路径上的重节点一定会变轻因为会左右子树交换，右路径上的轻节点不一定变重