频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
可并堆和左偏树问题解析
2017-07-17 09:52:17      个评论    来源:MaxMercer的博客  
收藏   我要投稿

堆?

对于堆大家想必是很熟悉的了,比如说stl里面的priority_queue就提供了方便的堆操作.当然更不必说pbds(戏称平板电视)里面的配对堆,更是Dijkstra优化的方便好手.简单的priority_queue能实现push,pop,取出top等操作...那么遇到两个堆的信息要合并的时候,我们如何实现呢?这里就是所要引出的概念——可并堆.

可并堆?

可并堆可以在log以内的时间复杂度合并两个堆,其中最优的当属斐波那契堆,但由于编程太过于复杂暂不提及.想到log,我们很容易想到平衡树为保持log的性质而使整棵树尽量平衡,今天要讲的左偏树实际上是有异曲同工之妙.左偏树是可并堆的一种,他编程简单,合并复杂度也是log级别的,这就好比平衡树里德treap(如果你不会treap的话请忽略...)

左偏树?

左偏树怎么做到log级别的合并的呢.左偏树,顾名思义,意思是整棵树是往左偏的.左边的字数"重量“更大,也就意味着,我们可以顺着右子树更快的找到可以插入的地方(深度更小).我们设dist为父节点到到可以插入的地方最少的经历的边数(注意堆为二叉树,一个节点有<=1的儿子就是可插入的,所以不一定可插入的地方就是叶子节点).左偏树的性质即为,右子树的dist一定小于等于左边的dist,这样来保持左偏树的性质.我们在合并两个堆的时候,也是顺着右子树往下找到可插的地方,再合并,.这样本来一直左偏(可以想象成一个天平),因为右子树合并了其他堆,所以整个天平又慢慢恢复平衡,也就保证了寻找并合并的快速(右子树dist小),近似log的复杂度.左偏树并非严格上的平衡,但只要维护左偏的性质,还是有着优秀的合并的速度.当然为了保持左偏树的性质,我们发现左子树的dist小于右子树的dist,就要swap交换字数。当然,左偏树作为一个堆,也要满足堆的性质:子节点的点值,大于父亲节点的点值(小根堆).下面为图解(某神犇的图).(若有点小可另存下来看一下).

\

\

\

结合代码理解一下:

struct Ltree{
	int dist[maxn],key[maxn],l[maxn],r[maxn];
	int merge(int x,int y){
	    if(x==0||y==0) return x+y;
	    if(key[x]dist[l[x]]) swap(l[x],r[x]);//如果右子树的dist大于左子树的dist,swap(左偏树的性质) 
	    dist[x]=dist[r[x]]+1;//父亲节点dist等于右子树的dist+1 
		return x;
	}
	void pop(int &x){x=merge(l[x],r[x]);}//等价于将左右子树合并的新堆,注意引用(&)来修改 
	int top(int x){return key[x];}	//直接返回key值即可 
}lt;
点击复制链接 与好友分享!回本站首页
上一篇:CSDN Markdown使用教程
下一篇:AWS 使用tag进行精细权限控制
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站