华为云计算 云知识 左偏树+菲波那切堆

左偏树+菲波那切堆

左偏树

维护对的性质,同时维护dis值保证合并复杂度

合并时类似于可持久化treap

左偏树+菲波那切堆1 左偏树+菲波那切堆2
#include
#include

inline int read() { int x=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar(); return x;
}
const int maxn = 100010;
struct node { int fa,dis,key,ch[2]; node() { key=fa=dis=0; }
}tree[maxn];
inline int ls(int x) {return tree[x].ch[0];}
inline int rs(int x) {return tree[x].ch[1];}
int n,m;
int find(int x) { if(tree[x].fa)  return find(tree[x].fa); else return x;
}
inline void update(int x) { tree[x].dis=tree[tree[x].ch[1]].dis+1;
}
int merge(int x,int y) { if(!x||!y)return x+y; if(tree[x].key>tree[y].key||(tree[x].key==tree[y].key&&x>y))std::swap(x,y); tree[x].ch[1]=merge(tree[x].ch[1],y); tree[tree[x].ch[1]].fa=x; if(tree[tree[x].ch[1]].dis>tree[tree[x].ch[0]].dis)std::swap(tree[x].ch[0],tree[x].ch[1]); update(x); return x;
}
void delet(int x) { int now=tree[x].fa;int top=merge(tree[x].ch[1],tree[x].ch[0]); tree[top].fa=now;tree[x].key=-1; while(now) { if(tree[tree[now].ch[0]].dis1]].dis)std::swap(tree[now].ch[0],tree[now].ch[1]); if(tree[now].dis==tree[tree[now].ch[1]].dis+1)return; tree[now].dis=tree[tree[now].ch[1]].dis+1; now=tree[now].fa; }
}
int main() { n=read(),m=read(); for(int i=1;i<=n;++i)>read(); while(m--) { int op=read(); if(op==1) { int x=read(),y=read(); if(tree[x].key==-1||tree[y].key==-1||x==y)continue; merge(find(x),find(y)); } else { int x=read(); if(tree[x].key==-1)puts("-1"); else x=find(x), printf("%d\n",tree[x].key), delet(x); } } return 0; 
}
左偏树

 

斐波那契堆

转载于:https://www.cnblogs.com/sssy/p/8029915.html

上一篇:Mongo技巧-连接数据库与修改表结构

下一篇:vue-cli3.0 使用postcss-plugin-px2rem(推荐)和 postcss-pxtorem(postcss-px2rem)自动转换px为rem 的配置方法;...

51CTO

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。