首页 > 代码库 > 左偏堆(模板)
左偏堆(模板)
#include <iostream> #include<cstdio> #define MAX 1010 using namespace std; int tot=0; int v[MAX],l[MAX],r[MAX],d[MAX];int merge(int x,int y){ if(x==0) return y; if(y==0) return x;//如果有一个子树是空 if(v[x]<v[y]) swap(x,y);//取较大的根节点权值 r[x]=merge(r[x],y);//将B合并入A的右子树 if(d[l[x]]<d[r[x]]) swap(l[x],r[x]);//维护左偏性质 d[x]=d[r[x]]+1;//更新距离。 return x;}int init(int x) //新建 { v[++tot]=x; l[tot]=r[tot]=d[tot]=0; return tot;}int insert(int x,int y)//新插入一个节点—先建一棵左偏树,再合并。{ merge(x,init(y));}int pop(int x)//删除堆顶元素。 { return merge(l[x],r[x]);}
左偏堆(模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。