浅谈随机堆

Simulated_annealing · 2026-07-06 18:56:04 · 算法·理论

前言

随机堆其实是一种很少有人写的数据结构，但是其实随机堆性能很好，维护简单，几乎可以完全替代左偏树。

随机堆效率等同于左偏树，而且代码极短，此外还支持可持久化。

此外，本文一般的堆指小根堆，且代码使用 C++ 编写。

算法介绍

这里以小根堆为例介绍。

现在以 P11266 【模板】可并堆 2 为模板题。

对于该题，以节点编号代表下标，以权值代表 a 的值。

什么是随机堆

随机堆是一种类似左偏树的可并堆，但是，不同的是随机堆没有左偏树的随机性质，而是通过随机来保证复杂度（所以也就意味着随机数质量要靠谱）。

随机堆什么性质也没有，甚至连完全二叉树都不是，但是确实是 O(\log n)。

对于随机堆，每个节点只需要维护 lc 左儿子，rc 右儿子，up 父节点，val 权值即可，没有左偏性质，无需维护 dist。

同左偏树一样，随机堆的最重要操作就是合并。

合并

合并是随机堆的最基本操作。

显然一种合并方法是：

1. 传入 x，y，表示现在要合并以 x，y 为根的树。
2. 若 x 和 y 有一个是空节点则返回另一个（从逻辑上看，若 x 和 y 均为空节点则应该返回空节点，虽然实际上不会出现）。
3. 若 val[x]>val[y] 则交换 x 和 y，此时保证 val[x]<val[y]。
4. 递归，将以 y 为根与以 rc[x]（其实 lc[x] 也可以）为根的子树合并。

然后你就会发现这棵树向右的链会越来越长，直接退化成接近链的样子，此时复杂度会退化到 O(n)（这里 n 指节点数）。

然后你肯定考虑一下两种方法：

1. 引入性质（引入左偏性质即为左偏树）。
2. 更改合并方式。

但是能否考虑左右子树交替使用呢？答案是不行，因为这也会导致一条左右交替的链越来越长。

其实只要但凡是确定性的方法使得在同一节点会使用同一子树就会导致一条链越来越长导致复杂度退化。

然后，你说，按次序分奇偶等等方法可行吗？其实，不可行，因为出题人也可以构造数据得到接近链的结构，只要出题人可以预测到合并左右子树的程序行为。

但是，此时若引入随机数，出题人是不可能预测随机数行为的，故无法构造数据来卡到链或接近链的结构。

尽管这是伪随机，但是鉴于出题人预测不了行为（有随机数种子，而且哪怕你使用固定随机数种子，出题人也不可能对着你的随机数种子出数据，虽然理论上能卡掉），外加伪随机数的统计特征与真随机无异，所以可以考虑其期望。

注意：尽管固定种子几乎不可能被卡，但是有风险，故不应该这样做。

于是就可以得出合并流程：

1. 传入 x，y，表示现在要合并以 x，y 为根的树。
2. 若 x 和 y 有一个是空节点则返回另一个，若 x 和 y 均为空节点则返回空节点。
3. 若 val[x]>val[y] 则交换 x 和 y，此时保证 val[x]<val[y]。
4. 以 \frac{1}{2} 的概率交换 lc[x] 和 rc[x]。
5. 递归，将以 y 为根与以 rc[x] 为根的子树合并。

int merge(int x,int y){
    if(!x||!y)return x+y;
    if(val[x]>val[y])swap(x,y);
    if(rng()&1)swap(lc[x],rc[x]);
    int t=merge(rc[x],y);
    rc[x]=t;
    up[t]=x;
    return x;
}

其中 rng 是随机数生成器。

这里呢，对于随机数生成器是有要求的，最低位的循环长度一定要长，但是对于随机数的大小是无所谓的。

复杂度分析

后面所有基于合并的操作复杂度显然等于合并的复杂度。

首先，令 h(T) 为 T 中到叶节点的随机路径长度。

合并会调用 \max(h(x),h(y)) 层，所以复杂度是 O(h(x)+h(y)) 的。

然后来分析 h(T) 的期望值，令 L,R 分别为 T 的左右子树。

设 T 有 n_T 个节点，L,R 有分别 n_L,n_R 个节点。

则有 n_T=n_L+n_R+1。

然后假设 E(h(t))\le\log(n+1)。

归纳成立，所以 E(h(T))=O(\log n)。

可以得知这样树高的期望是 O(\log n) 的，即合并的复杂度是期望 O(\log n) 的，证明看这里。

链接里提到了一个结论（这里不放证明了），这个结论是 {\cal P}(h(T)>(c+1)\log n)=\frac{1}{n}。

我们来体现一下这个概率多低呢？

对于一道正常题目，n=10^6 然后 h(T)>5\log n 的概率为 10^{-24}，未必高于测评机故障的概率。

而且，若是 h(T)>10\log n 的话，概率为 10^{-54}，这几乎不可能，这个概率大约是在 10000 个地球中精准命中 1 个指定原子，假设你每秒尝试一次你需要尝试 2.5\times 10^{36} 个宇宙当前年龄。

这告诉我们，当你的随机数没有被预测并卡掉的情况下（即假设完全随机），你是不可能被卡掉的。

所以，随机堆是可以放心使用的正经 O(\log n) 算法。

插入

其实就是将单点视为一个堆去合并。

在该题中需要向集合 S_x 插入一个节点编号为 y 值为 a_y 的元素。

void insert(int x,int id){
    rt[x]=merge(rt[x],id);
}

删除最小元素

其实就是下面删除任意元素的特殊情况。

void del(){
    rt=merge(lc[rt],rc[rt]);
}

删除任意元素

第二复杂的操作，不过也很短，比左偏树短多了。

首先，需要知道该元素对应的节点编号（这也是最上面那句话的原因）。

对于该题，以节点编号代表下标，以权值代表 a 的值。

其实就是要把该节点的左右子树合并就行了。

然后分类一下，若该点为某个堆的根节点，那么更新根节点，否则更新父节点的一个子节点。

在该题中，存在节点重复使用，我们应该清空被删除节点的数据。

对于一般题目，我们其实也应该这样做。

void del(int x,int id){
    int t=merge(lc[id],rc[id]);
    if(rt[x]==id)rt[x]=t;
    else{
        up[t]=up[id];
        if(lc[up[id]]==id)lc[up[id]]=t;
        if(rc[up[id]]==id)rc[up[id]]=t;
    }
    lc[id]=rc[id]=up[id]=0;
}

查询

只需要返回根节点的 val 即可。

int query(int x){
    return val[x];
}

建堆

只需要当成正常的堆建堆就行（因为没有性质）。 可以自己到 OI-wiki 上看（没错，就看二叉堆就行了），但是要维护 lc 和 rc（为了合并操作的正常进行）。

这样可以 O(n) 建堆，但是其实在不卡建堆时间时考虑逐个插入其实更方便，外加常数也很优秀，只不过这样是 O(n\log n) 的。

模板题

操作 0 即为上文删除任意元素。

操作 1 即为上文查询。

操作 2 即为上文合并。

操作 3 实则是删除然后重新插入。

del(x,y);
val[y]=z;
insert(x,y);

然后写出代码即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;
int rt[N],lc[N],rc[N],val[N],up[N];
mt19937 rng(time(0));
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(val[x]>val[y])swap(x,y);
    if(rng()&1)swap(lc[x],rc[x]);
    int t=merge(rc[x],y);
    rc[x]=t;
    up[t]=x;
    return x;
}
void del(int x,int id){
    int t=merge(lc[id],rc[id]);
    if(rt[x]==id)rt[x]=t;
    else{
        up[t]=up[id];
        if(lc[up[id]]==id)lc[up[id]]=t;
        if(rc[up[id]]==id)rc[up[id]]=t;
    }
    lc[id]=rc[id]=up[id]=0;
}
void insert(int x,int id){
    rt[x]=merge(rt[x],id);
}
int query(int x){
    return val[x];
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&val[i]);
        rt[i]=i;
    }
    while(m--){
        int op,x,y,z;
        scanf("%d",&op);
        if(op==0){
            scanf("%d%d",&x,&y);
            del(x,y);
        }else if(op==1){
            scanf("%d",&x);
            printf("%d\n",query(rt[x]));
        }else if(op==2){
            scanf("%d%d",&x,&y);
            rt[x]=merge(rt[x],rt[y]);
            rt[y]=0;
        }else if(op==3){
            scanf("%d%d%d",&x,&y,&z);
            del(x,y);
            val[y]=z;
            insert(x,y);
        }
    }
    return 0;
}

此外，若没有删除任意元素操作，这无需维护 up。

相较于左偏树而言，几乎没有缺点，有点在于不需要维护 dist 也不需要写 pushup。

唯一缺点是不确定，但是上面也讨论过概率问题。

简单应用

题目：P2713 罗马游戏

题意分析

初始情况：每个集合中有一个元素。 操作：

1. 合并两个集合。
2. 删除一个集合的最小值并输出。

鉴于需要判断是否为死人，需要开一个 dead 维护此人是否被杀。对于合并呢，就用并查集。

操作 1 就是上文的合并。

操作 2 就是查询并删除。

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+50;
mt19937 rng(time(0));
bitset<N>dead;
int fa[N];
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int val[N],lc[N],rc[N],rt[N];
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(val[x]>val[y])swap(x,y);
    if(rng()&1)swap(lc[x],rc[x]);
    rc[x]=merge(rc[x],y);
    return x;
}
int query(int x){
    return val[rt[x]];
}
void del(int x){
    rt[x]=merge(lc[rt[x]],rc[rt[x]]);
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&val[i]);
        fa[i]=i;
        rt[i]=i;
    }
    int m;
    scanf("%d",&m);
    while(m--){
        char c=getchar();
        while(c!='M' && c!='K')c=getchar();
        if(c=='M'){
            int x,y;
            scanf("%d%d",&x,&y);
            if(dead[x]||dead[y])continue;
            x=find(x);
            y=find(y);
            if(x==y)continue;
            fa[y]=x;
            rt[x]=merge(rt[x],rt[y]);
        }else{
            int x;
            scanf("%d",&x);
            if(dead[x]){
                puts("0");
                continue;
            }
            x=find(x);
            printf("%d\n",query(x));
            dead[rt[x]]=1;
            del(x);
        }
    }
    return 0;
}

习题：P4971 断罪者。 这题其实很简单。

扩展应用

带标记可并堆

P3261 [JLOI2015] 城池攻占

相信前面的两道青题和一道蓝题应该已经足够理解随机可并堆的板子了，那么来一道复杂一点的。

这是一个树上问题，用可并堆的话来讲，就是 6 种操作。

操作 1，将集合中所有元素加上某数。

操作 2，将集合中所有元素乘上某正数。

操作 3，合并两个集合。

操作 4，删除最小值。

操作 5，查询最小值。

操作 6，插入元素。

对于操作 1,2 不改变堆结构，所以可以打标记。

用题目的话来讲，就是对于每个城池有一个集合，找到最弱骑士并判断是否牺牲，然后留下所有可以通过该城池的所有骑士并改变战力，然后于父节点的集合合并。

对于操作 1,2 打标记是 O(1) 的，一共 O(n)，传标记单次是 O(1) 的。

对于操作 3 每层递归为 O(1)，递归 O(\log m) 层，故复杂度为 O(\log m)，一共为 O(n\log m)。

对于操作 4 即为合并操作为 O(\log m)，然而每个骑士只能至多死一次，故调用 O(m) 次，一共 O(m\log m)。

对于操作 5 一次只会查询所有在该城池死掉的骑士和一个不死的骑士，调用 O(n+m) 次，单次 O(1) 一共 O(n+m)。

对于操作 6 仅在开始时调用 m 次，单次 O(m\log m)，一共 O(m\log m)。

鉴于 n,m 同阶，复杂度为 O(n\log n)。

主要就是标记下传有亿点点难搞。

鉴于乘法是高于加法的，所以乘法下传时不仅要将子节点的乘法标记相乘，而且还要取与加法标记相乘。

void pushdown(int x){
    ll add=tagadd[x],mul=tagmul[x];
    tagadd[x]=0;
    tagmul[x]=1;
    if(lc[x]){
        val[lc[x]]=val[lc[x]]*mul+add;
        tagadd[lc[x]]=tagadd[lc[x]]*mul+add;
        tagmul[lc[x]]=tagmul[lc[x]]*mul;
    }
    if(rc[x]){
        val[rc[x]]=val[rc[x]]*mul+add;
        tagadd[rc[x]]=tagadd[rc[x]]*mul+add;
        tagmul[rc[x]]=tagmul[rc[x]]*mul;
    }
}

然后就是为了简单考虑加上新标记时要先下推标记。 于是代码就好了。

#include<bits/stdc++.h>
using namespace std;
constexpr int N=3e5+50,M=3e5+50;
typedef long long ll;
mt19937 rng(time(0));
int rt[N],lc[M],rc[M];
ll val[M],tagadd[M],tagmul[M];
int f[N],a[N],c[M];
ll v[N],h[N],s[N];
int ans[N],pos[M],dep[N];
void pushdown(int x){
    ll add=tagadd[x],mul=tagmul[x];
    tagadd[x]=0;
    tagmul[x]=1;
    if(lc[x]){
        val[lc[x]]=val[lc[x]]*mul+add;
        tagadd[lc[x]]=tagadd[lc[x]]*mul+add;
        tagmul[lc[x]]=tagmul[lc[x]]*mul;
    }
    if(rc[x]){
        val[rc[x]]=val[rc[x]]*mul+add;
        tagadd[rc[x]]=tagadd[rc[x]]*mul+add;
        tagmul[rc[x]]=tagmul[rc[x]]*mul;
    }
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    pushdown(x),pushdown(y);
    if(val[x]>val[y])swap(x,y);
    if(rng()&1)swap(lc[x],rc[x]);
    rc[x]=merge(rc[x],y);
    return x;
}
void del(int x){
    if(!rt[x])return ;
    pushdown(rt[x]);
    rt[x]=merge(lc[rt[x]],rc[rt[x]]);
}
void Add(int x,ll v){
    if(!rt[x])return ;
    pushdown(rt[x]);
    val[rt[x]]+=v;
    tagadd[rt[x]]=v;
}
void Mul(int x,ll v){
    if(!rt[x])return ;
    pushdown(rt[x]);
    val[rt[x]]*=v;
    tagmul[rt[x]]=v;
}
ll query(int x){
    if(!rt[x])return 2e18;
    return val[rt[x]];
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&h[i]);
    }
    dep[1]=1;
    for(int i=2;i<=n;++i){
        scanf("%d%d%lld",&f[i],&a[i],&v[i]);
        dep[i]=dep[f[i]]+1;
    }
    for(int i=1;i<=m;++i){
        scanf("%lld%d",&s[i],&c[i]);
        val[i]=s[i];
        tagmul[i]=1;
        rt[c[i]]=merge(rt[c[i]],i);
    }
    for(int i=n;i>=1;--i){
        while(query(i)<h[i]){
            ++ans[i];
            pos[rt[i]]=i;
            del(i);
        }
        if(a[i]==0)Add(i,v[i]);
        if(a[i]==1)Mul(i,v[i]);
        rt[f[i]]=merge(rt[f[i]],rt[i]);
    }
    for(int i=1;i<=n;++i){
        printf("%d\n",ans[i]);
    }
    for(int i=1;i<=m;++i){
        printf("%d\n",dep[c[i]]-dep[pos[i]]);
    }
    return 0;
}

有个细节是存活到最后的骑士 pos 为 0，而 dep[0]=0 正好是正确的。

query 中对于空集返回足够大的值为了保证不会进行删除操作。

可持久化随机堆

实则只需要更改 merge，要先复制再递归合并。

int merge(int x,int y){
    if(!x||!y)return x+y;
    if(val[x]>val[y])swap(x,y);
    int p=newnode(x);
    if(rng()&1)swap(lc[p],rc[p]);
    rc[p]=merge(rc[p],y);
    return p;
}

后记

作为一个坚定的随机爱好者，在打模板题时遇到了可并堆，然后再 OI-wiki 学习后结合已有的左偏树等写法写出了随机堆，希望可以为洛谷提供一份完整的随机堆模板（虽然也还不完整），也希望有更多人可以学到随机堆。

相信看完整篇文章，就可以明白随机堆的优点和常见用法。

祝大家学习愉快。

主要参考 OI-wiki （左偏树），OI-wiki （堆简介），cp-algorithms.com。

此外，在学习过程中有运用过 Deepseek，但是 Deepseek 生成的内容并未出现在文章中。