首页 > 代码库 > 左偏堆(模板)

左偏堆(模板)

#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]);}

 

左偏堆(模板)