随机堆

一、界说

随机堆是一种时间复杂度与左偏树相近，代码巨短的可并堆。随机数完胜 dis 数组。
二、一些根本操纵

• 归并 \(x\) 和 \(y\)。
  

1. int merge(int x,int y){
2.     if(!x||!y) return x|y;
3.     if(val[x]>val[y]) swap(x,y);
4.     if(rnd()&1) swap(ls[x],rs[x]);
5.     int t=merge(rs[x],y);rs[x]=t,fa[t]=x;
6.     return x;
7. }

复制代码

各有 \(50\%\) 概率走左边或右边。

• 在 \(x\) 中删除 \(id\)。
  

1. void del(int x,int id){
2.     int t=merge(ls[id],rs[id]);
3.     if(rt[x]==id) rt[x]=t;
4.     else{
5.         fa[t]=fa[id];
6.         if(ls[fa[id]]==id) ls[fa[id]]=t;
7.         if(rs[fa[id]]==id) rs[fa[id]]=t;
8.     }
9.     ls[id]=rs[id]=fa[id]=0;
10. }

复制代码

分 \(id\) 为根和非根的情况。
三. 时间复杂度证实。

渴望随机路径长度为 \(E(h(T))\)。令 \(L,R\) 为 \(T\) 的左右子树。
用 \(n\) 体现节点数，那么有 \(n_T=n_L+n_R+1\)。
假设 \(E(h(t))\le O(\log(n+1))\)。归纳证实：

\[\begin{aligned}E(h(T))&=\frac{E(h(L))+E(h(R))}{2}+1\\&\le \frac{\log(n_L+1)+\log(n_R+1)}{2}+1\\&=\log 2\sqrt{(n_L+1)(n_R+1)}\\&\le \frac{2\log((n_L+1)+(n_R+1))}{2}\\&=\log(n_L+n_R+2)\\&=O(n+1)\end{aligned}\]
归纳创建。
四、与其他堆的对比

堆范例归并删除代码长度（相对）维护信息优点随机堆渴望 \(O(\log n)\)渴望 \(O(\log n)\)极短左右孩子 + 父指针左偏树最坏 \(O(\log n)\)最坏 \(O(\log n)\)较短左右孩子 + dis斐波那契堆均派 \(O(1)\)均派 \(O(\log n)\)很长复杂的多域标志五、例题

• 洛谷 P11266【模板】可并堆 2
  

板子题。

1. #includeusing namespace std;const int N=1e6+5;int n,m,rt[N],ls[N],rs[N],fa[N],val[N];mt19937 rnd(time(0));int merge(int x,int y){
2.     if(!x||!y) return x|y;
3.     if(val[x]>val[y]) swap(x,y);
4.     if(rnd()&1) swap(ls[x],rs[x]);
5.     int t=merge(rs[x],y);rs[x]=t,fa[t]=x;
6.     return x;
7. }void del(int x,int id){
8.     int t=merge(ls[id],rs[id]);
9.     if(rt[x]==id) rt[x]=t;
10.     else{
11.         fa[t]=fa[id];
12.         if(ls[fa[id]]==id) ls[fa[id]]=t;
13.         if(rs[fa[id]]==id) rs[fa[id]]=t;
14.     }
15.     ls[id]=rs[id]=fa[id]=0;
16. }void insert(int x,int id){rt[x]=merge(rt[x],id);}int qval(int x){return val[x];}int main(){    srand(time(0));    scanf("%d %d",&n,&m);    for(int i=1;i>=1,b=merge(b,fy);            printf("%d\n",val[merge(a,b)]);        }    }    return 0;}

复制代码

六、总结

随机堆大法好~