【模板】可并堆

发表于

之前写的太丑了

可并堆插入的值和num是一直对应的
如果按顺序new_node
那么不管怎么修改，t[i].val=a[i]
主体：

1
2
3
4
5
6
7
8
9
struct node{
	int val,fa,ls,rs;
	inline node(int _val=0,int _fa=0,int _ls=0,int _rs=0)
	{
		val=_val;fa=_fa;ls=_ls;rs=_rs;
	}
};
node t[N];
int num;

初始化清空：

1
2
3
4
inline void clear()
{
	num=0;
}

加新点：

1
2
3
4
5
6
inline int new_node(int x)
{
	++num;
	t[num]=node(x);
	return num;
}

合并两个堆：

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

找所在的堆：

1
2
3
4
5
inline int get_fa(int x)
{
	while(t[x].fa)	x=t[x].fa;
	return x;
}

删除堆顶：

1
2
3
4
5
6
inline void pop(int x)//改成int，把merge的结果return就可以知道新的根
{
	t[x].val=0;
	t[t[x].ls].fa=t[t[x].rs].fa=0;
	merge(t[x].ls,t[x].rs);
}