【学习笔记】配对堆学习笔记

配对堆是一种 被猜想 能均摊 $O(\log n)$ 删除,其余 所有 操作(包括但不限于 $\text{top}, \text{make-heap}, \text{decrease-key}, \text{meld}$ 等)均摊 $O(1)$ 的数据结构。

pdf 论文

Warning: 这真的是一篇 学习笔记,只尝试着解释论文中一些(也许)不那么显而易见的内容,并不给出配对堆的完整实现。

  1. 随意排列子结点链表最坏可使 $\text{delete min}$ 操作达到 $O(\sqrt{n})$。

    证明如下:

    定义一棵 $n$ 个点的树中有 $d$ 个孩子的结点 $u$ 的势能 $\Phi(u) = 1 - \min\{d, \lfloor\sqrt{n}\rfloor\}$。

    我们将 $\text{delete min}$ 操作拆成 $\text{delete}$ 和 $\text{pair}$ 两个操作。

    那么将根节点 $root$ 移去时,根节点的势能原来是 $\Phi(root) = 1 - \lfloor\sqrt{n}\rfloor$,现在变成了 $0$,则最多会导致 $\sqrt{n}$ 的势能 增加

    剩下的每个子结点的势能我们这么计算:

    如果有已经达到 $\sqrt{n}$ 个子结点的某个点 $u \in son(root)$,则 $\Phi(u) = 1 - d$。根节点的移除会使 $\Phi(u)’ = 1 - (d - 1) = 2 - d$,即 $\Phi(u)’ = \Phi(u) + 1$。

    不难看出最多只会有 $\sqrt{n}$ 个这样的点,因此这样也最多会导致 $\sqrt{n}$ 的势能 增加

    综上所述,$\text{delete}$ 操作最多会引起 $2\sqrt{n}$ 的势能 增加

    不妨设移除根后有 $k$ 个儿子,则我们会用 $\lfloor\dfrac{k}{2}\rfloor + 1$ 次 $\text{link}$ 操作。

    注意到 $\text{link}$ 两个已经有 $\sqrt{n}$ 个儿子的结点 并不会引起 势能的变化,而最多会有 $\sqrt{n}$ 个这样的结点。

    所以 $\text{pair}$ 操作会导致 $\lfloor\dfrac{k}{2}\rfloor - \sqrt{n}$ 的势能 减少

    那么 $\text{delete min}$ 操作的均摊复杂度是 $(\lfloor\dfrac{k}{2}\rfloor + 1) + 2\sqrt{n} - (\lfloor\dfrac{k}{2}\rfloor - \sqrt{n}) = O(\sqrt{n})$ 的。

  2. 除 $\text{find min}$ 和 $\text{make heap}$ 操作均摊 $O(1)$ 外,其余操作的时间复杂度是均摊 $O(\log n)$ 的。

    证明如下:

    设 $s(u)$ 表示 $u$ 所在子树的大小,定义一个结点 $u$ 的势能 $\Phi(u) = \sum_{v \in \text{subtree of } u}\log_2s(v)$。

    现在我们用 $\log$ 来简写 $\log_2$。

    $\text{insert}, \text{meld}, \text{decrease key}$ 的时间复杂度比较好分析。

    当我们在 $\text{link}(u, v)$ 时,$\Phi(u)$ 和 $\Phi(v)$ 将会变化,不妨设 $v \to u$

    那么 $\Phi(v)$ 最多会有 $\log n$ 的势能 增加,$\Phi(u)$ 最多会有 $1$ 的势能增加。

    显然这三个操作的时间复杂度是均摊 $O(\log n)$ 的。

    下面我们来重点分析 $\text{delete min}$ 操作。

    1.png

    我们来看这么一个图,即 $\text{link}(x, y)$ 后的变化。

    我们先分析第一轮 $\text{pairing}$ 的时间复杂度。

    注:$x, y \in \mathbb{R_+}, x + y \le 1$ 时 $\log x + \log y$ 的最大值为 $-1$(初中内容)。

    $\begin{aligned}\Delta\Phi = \Phi_1 - \Phi_2 & = rank(x) + rank(y) - rank(x’) - rank(y’) \\ & = \log (s(a) + s(b) + s(c) + 2) + \log(s(b) + s(c) + 1) - \log(s(a) + s(b) + 1) - \log(s(b) + s(c) + 1) \\ & = \log(s(a) + s(b) + 1) - \log(s(b) + s(c) + 1)\end{aligned}$

    $\begin{aligned}\therefore & \log(s(a) + s(b) + 1) + \log(s(c)) - 2\log(s(a) + s(b) + s(c) + 2) \\ & = \log\dfrac{s(a) + s(b) + 1}{s(a) + s(b) + s(c) + 2} + \log\dfrac{s(c)}{s(a) + s(b) + s(c) + 2} \\ & \le -2 \end{aligned}$(这里用了刚才的

    又 $\log s(c) \le \log(s(b) + s(c) + 1)$

    $\therefore \log(s(a) + s(b) + 1) - \log(s(b) + s(c) + 1) \le 2\log(s(a) + s(b) + s(c) + 2) - 2\log s(c) - 2$

    $\because s(x) = s(a) + s(b) + s(c) + 2$

    $\Delta\Phi \le 2\log s(x) - 2\log s(c) - 2$

    $\therefore$ $2\log s(x) - 2\log s(c) - 2$ 是 $\text{link}$ 能达到的势能 增加 最大值。

    当且仅当 $c = \varnothing$ 时取得最大值。

    则总势能变化量

    $\begin{aligned}\Sigma\Phi & = \sum\limits_{i - 1}^{k - 1}(2 \log s(x_{2i - 1}) - 2 \log s(x_{2i}) - 2) + 2 \log s(x_{2k - 1}) \\ & = \sum\limits_{i - 1}^{k - 1}(2 \log s(x_{2i - 1}) - 2 \log s(x_{2i})) + 2 \log s(x_{2k - 1}) - 2(k - 1) \\ & \le \sum\limits_{i = 1}^{k - 1}(2 \log s(x_{2i - 1}) - 2 \log s(x_{2i + 1})) + 2 \log s(x_{2k - 1}) - 2(k - 1) \\ & = 2 \log s(x_1) - 2(k - 1) \\ & = 2 \log n - 2(k - 1)\end{aligned}$

    而旧根的删除会使总势能 减少 $\Phi(root) = \log n$,而最后只会有新根的势能会 增加 $\Phi’ = \log(n - 1)$。

    综上所述,$\text{delete min}$ 的时间复杂度为均摊 $O(\log n)$。

作者

Clever_Jimmy

发布于

2020-03-16

更新于

2020-05-06

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×