之前写的太丑了
可并堆插入的值和num是一直对应的
如果按顺序new_node
那么不管怎么修改，t[i].val=a[i]
主体：
1 2 3 4 5 6 7 8 9
|
struct { int val,fa,ls,rs; inline (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) { t[x].val=0; t[t[x].ls].fa=t[t[x].rs].fa=0; merge(t[x].ls,t[x].rs); }
|
近期评论