Randomized Heap / 随机堆

· · 算法·理论

Randomized Heap / 随机堆

——一种简单易实现的可并堆

介绍

以下所说的堆默认为小根堆。

随机堆是一种可并堆，可以在期望 \mathcal O(\log n) 复杂度内实现以下操作：

在实现上，随机堆的实现难度较为容易，略易于左偏树等常见可并堆。

操作

随机堆的核心操作是合并（merge）：

算法 1. 合并

设当前要合并分别以 x,y 为根的堆 \mathcal P,\mathcal Q。不妨设 x 的值小于 y 的值，因此 x 将充当新堆的根。随机选取 x 的左子树或者右子树之一，记作堆 \mathcal T，将 \mathcal T 与 \mathcal Q 合并作为 x 新的左子树或右子树（取决于之前的选取）。重复以上算法直到 \mathcal P, \mathcal Q 其中之一为空堆。

int merge(int x, int y) {
    if (!x || !y) return x ^ y;
    if (t[x].val > t[y].val) swap(x, y);
    int& son = rnd() & 1 ? t[x].ls : t[x].rs;
    son = merge(son, y);
    t[son].fa = x;
    return x;
}

实际使用中，应使用质量较高的随机数生成器，比如 std::mt19937 而不是 rand()。

有了合并操作，其他操作是平凡的。

算法 2. 添加元素

将新的元素视作单点堆，合并原堆与新元素的堆作为新堆。

算法 3. 删除堆顶

合并根的左子树和右子树作为新堆。

算法 4. 减少元素的值

要求已知该元素对应的节点为 x。断开 x 和父亲的边，直接修改 x 节点的值，合并 以 x 为根的堆和原堆作为新堆。

算法 5. 移除元素

将该元素的值减少为 -\infty，这将会使其移动到堆顶。删除堆顶。

以上操作的复杂度全部基于合并操作的复杂度，为期望 \mathcal O(\log n)。

算法 6. 查询最小值

直接查询根的值即可。复杂度为 \mathcal O(1)。

复杂度分析

一个含有 n 个元素的随机堆有 n 个节点，因此空间复杂度为 \mathcal O(n)。

下面给出时间复杂度的证明。

引理

对于任意一棵 N 个节点的二叉树 \mathcal T。从根节点出发，每步随机走左儿子或右儿子（即使是空节点），令首次到达空节点的期望步数为 E[\mathcal T]，则：

E[\mathcal T] \le \log_2(N + 1)

证明

采用归纳法，当 N = 0 时命题显然成立。

假设对于所有的 N_0 \le N - 1 命题成立。对于一棵 N 个节点的二叉树 \mathcal T，令其左子树为 \mathcal L，右子树为 \mathcal R，节点个数分别为 A,B。则有期望递推：

E[\mathcal T] = \frac 1 2(E[\mathcal L] + E[\mathcal R]) + 1

由于 A,B \le N - 1，应用归纳假设得到：

\begin{align} E[\mathcal T] &\le \frac 1 2(\log_2(A+1) + \log_2(B+1)) + 1 \\ &= \frac 1 2 \log_2[(A+1)(B+1)] + 1 \\ &= \log_2\sqrt{(A+1)(B+1)} + \log_2 2 \\ &= \log_2 2\sqrt{(A + 1)(B + 1)} \end{align}

显然 A + B = N - 1，由基本不等式得：

2\sqrt{(A + 1)(B + 1)} \le A + B + 2 = N + 1

因此：

E[\mathcal T] \le \log_2(N+1)

可见命题对于 N 也成立，归纳得对于所有的 N \in \N^* 命题成立。\blacksquare

上述引理还有一个有趣的性质是：当且仅当 A = B 时不等式取等号。这意味着，一棵完美二叉树的期望步数是最大的，而最不平衡的链的期望步数反而是最小的。

借助引理，我们就能给出随机堆时间复杂度的证明：

定理

随机堆合并操作的复杂度为期望 \mathcal O(\log n)。

证明

考察合并操作时两个堆根的变化，这本质上是在两棵二叉树上从根节点出发做随机游走。每递归一层，其中一棵树的当前节点将会向下走一步变为新的堆根，直到其中一个节点走到空节点。根据引理，其期望步数小于为 \mathcal O(\log n)，因此合并操作的复杂度为 \mathcal O(\log n)。\blacksquare

由于复杂度不是均摊的，因此随机堆是可持久化的。