左偏树模板 - #include <Seter> - using namespace Orz;

左偏树模板

Seter posted @ 2011年11月10日 18:13 in Practice with tags MergeableHeap , 2025 阅读

左偏树真是个超好写的东西!支持合并,插入,删除最小值三个操作。后两个操作都可以看成第一个操作的拓展,如删除最小值是合并根的两棵子树,插入则直接将元素看作一个左偏树——所以只要写个Merge就可以了!

左偏树保证左子树深度大于等于右子树深度,同时符合堆性质。合并LT1,LT2(假设LT1中最小值比LT2小,否则交换)时,递归合并LT1的右子树和LT2替换掉LT1,然后如果LT1不符合左偏性质,则交换LT1的子树。

小小的提示:构树时,逐个插入是O(nlgn)的。这里可以有O(n)的复杂度的算法:先把所有元素构成n个单元素左偏树放进队列,然后每次取出两个合并后放入队列尾,直到只剩下一棵左偏树。

#include <stdio.h>
#include <string.h>
#define maxn 100000
#define Type int
#define cmp(x,y) ((x)<(y))
typedef struct _LT{struct _LT *c[2];Type v;int d;}LT,*PLT;
LT st[maxn],*stp=st;
PLT Merge(PLT LT1,PLT LT2){
	PLT t;
	if(!LT1)return LT2;if(!LT2)return LT1;
	if(cmp(LT2->v,LT1->v))t=LT1,LT1=LT2,LT2=t;
	LT1->c[1]=Merge(LT1->c[1],LT2);
	if(!LT1->c[0]||LT1->c[0]->d<LT1->c[1]->d)t=LT1->c[0],LT1->c[0]=LT1->c[1],LT1->c[1]=t;
	return (LT1->d=LT1->c[0]?LT1->c[0]->d+1:0),LT1;
}inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}main(){
	return 0;
}
By Seter
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee