第 4 周：左偏树和斜堆

左偏树

Null 路径长度

Npl(x) 代表从 x 往下到它的最近的 null 结点所需要的路程。Npl(null) = 1。

性质

• 如果一棵左偏树从根一直往右走的路径上面有 r 个结点，那么这棵树最少有 \(2^r - 1\) 个结点。
• 相应的，一个结点数为 N 的左偏树的右路径最长是 \(\lfloor \log (N + 1) \rfloor\)。

斜堆

这是一个均摊时间复杂度 \(O(M \log N)\) 的东西，N 是结点个数，M 是操作数。

和左偏树的区别是并不维护 Npl。合并的时候总会交换左右儿子。

摊还分析

现在要进行 n 次合并操作，最终最多有 n 个结点（每次都插入）。

• 重结点是右子树结点数量大于左子树结点数量的结点，其他结点叫做轻结点。
• 势能 \(\Phi(i)\) 是第 i 次合并后重结点的数量；很明显 \(\Phi(i) < n\)。

现在是第 i 次合并，需要合并两个堆 a 和 b。它们右路径上面轻、重结点个数分别是 \(l_a, h_a, l_b, h_b\)。（合并时只有右路径上的结点轻重状态可能变化。）

这一次合并的实际开销是 \(c_i = l_a + h_a + l_b + h_b\)。

合并后所有的重结点都会变成轻结点。最坏情况是所有的轻结点都变成重结点。注意此时一条右路径上的轻结点的数量小于 \(\log n\)（右子堆结点数小于等于左子堆结点数）。

所以势能变化是 \(\Delta \Phi \leq l_a + l_b - h_a - h_b\)。

\[\begin{aligned} \hat{c_i} & = \Delta \Phi + c_i \\ & \leq 2 (l_a + l_b) \\ & \leq 2 \log n \end{aligned}\]

那么 n 次的均摊开销是

\[\begin{aligned} \sum_{i=1}^{n}{c_i} + \Phi(n) - \Phi(0) & = \sum_{i=1}^{n}{\hat{c_i}} \\ \sum_{i=1}^{n}{c_i} + \Phi(n) - \Phi(0) & \leq 2 n \log n \\ \sum_{i=1}^{n}{c_i} & \leq n + 2n \log n \end{aligned}\]

就是这样。