欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

可并堆?左偏树?

程序员文章站 2024-02-13 14:33:34
...

        堆?

          对于堆大家想必是很熟悉的了,比如说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]<key[y]) swap(x,y);//堆的基本性质 
	    r[x]=merge(r[x],y);
	    if(dist[r[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;
          一道基础的左偏树题目可并堆?左偏树?:bzoj2809 点这里 (含题解及代码,可以用主席树做,但是最好用左偏树练练手);

          The End.

相关标签: 可并堆 左偏树