柳州学校网站建设,辽阳公司做网站,wordpress中怎么排序,凡科建站做的网站收录慢吗2.1.2 可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型#xff0c;它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)#xff0c;还支持一个额外的操作——合并操作#xff1a; H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆…2.1.2 可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)还支持一个额外的操作——合并操作 H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 O(n)用它来实现可并堆则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树在后面我们将看到各种可并堆的比较。 2.2 左偏树的定义 左偏树(Leftist Tree)是一种可并堆的实现。左偏树是一棵二叉树它的节点除了和二叉树的节点一样具有左右子树指针( left, right )外还有两个属性键值和距离(dist)。键值上面已经说过是用于比较节点的大小。距离则是如下定义的 节点i称为外节点(external node)当且仅当节点i的左子树或右子树为空 ( left(i) NULL或right(i) NULL )节点i的距离(dist(i))是节点i到它的后代中最近的外节点所经过的边数。特别的如果节点i本身是外节点则它的距离为0而空节点的距离规定为-1 (dist(NULL) -1)。在本文中有时也提到一棵左偏树的距离这指的是该树根节点的距离。 左偏树满足下面两条基本性质 [性质1] 节点的键值小于或等于它的左右子节点的键值。 即key(i)≤key(parent(i)) 这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1我们可以知道左偏树的根节点是整棵树的最小节点于是我们可以在O(1) 的时间内完成取最小节点操作。 [性质2] 节点的左子节点的距离不小于右子节点的距离。 即dist(left(i))≥dist(right(i)) 这条性质称为左偏性质。性质2是为了使我们可以以更小的代价在优先队列的其它两个基本操作插入节点、删除最小节点进行后维持堆性质。在后面我们就会看到它的作用。 这两条性质是对每一个节点而言的因此可以简单地从中得出左偏树的左右子树都是左偏树。 由这两条性质我们可以得出左偏树的定义左偏树是具有左偏性质的堆有序二叉树。 2.3 左偏树的性质 在前面一节中本文已经介绍了左偏树的两个基本性质下面本文将介绍左偏树的另外两个性质。 我们知道一个节点必须经由它的子节点才能到达外节点。由于性质2一个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数也就是说我们有 [性质3] 节点的距离等于它的右子节点的距离加1。 即 dist( i ) dist( right( i ) ) 1 外节点的距离为0由于性质2它的右子节点必为空节点。为了满足性质3故前面规定空节点的距离为-1。 我们的印象中平衡树是具有非常小的深度的这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有的节点而设计的它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。从图中我们可以看到它并不平衡由于性质2的缘故它的结构偏向左侧不过距离的概念和树的深度并不同左偏树并不意味着左子树的节点数或是深度一定大于右子树。 下面我们来讨论左偏树的距离和节点数的关系。 [引理1] 若左偏树的距离为一定值则节点数最少的左偏树是完全二叉树。 证明由性质2可知当且仅当对于一棵左偏树中的每个节点i都有 dist(left(i)) dist(right(i)) 时该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。 [定理1] 若一棵左偏树的距离为k则这棵左偏树至少有2k1-1个节点。 证明由引理1可知当这样的左偏树节点数最少的时候是一棵完全二叉树。距离为k的完全二叉树高度也为k节点数为2k1-1所以距离为k的左偏树至少有2k1-1个节点。 作为定理1的推论我们有 [性质4] 一棵N个节点的左偏树距离最多为ëlog(N1)û -1。 证明设一棵N个节点的左偏树距离为k由定理1可知N ≥ 2k1-1因此k ≤ ëlog(N1)û -1。 有了上面的4个性质我们可以开始讨论左偏树的操作了。 三、左偏树的操作 本章将讨论左偏树的各种操作包括插入新节点、删除最小节点、合并左偏树、构建左偏树和删除任意节点。由于各种操作都离不开合并操作因此我们先讨论合并操作。 3.1 左偏树的合并 C ← Merge(A,B) Merge( ) 把A,B两棵左偏树合并返回一棵新的左偏树C包含A和B中的所有元素。在本文中一棵左偏树用它的根节点的指针表示。 在合并操作中最简单的情况是其中一棵树为空也就是该树根节点指针为NULL。这时我们只须要返回另一棵树。 若A和B都非空我们假设A的根节点小于等于B的根节点否则交换A,B把A的根节点作为新树C的根节点剩下的事就是合并A的右子树right(A) 和B了。 right(A) ← Merge(right(A), B) 合并了right(A) 和B之后right(A) 的距离可能会变大当right(A) 的距离大于left(A) 的距离时左偏树的性质2会被破坏。在这种情况下我们只须要交换left(A) 和right(A)。 若dist(left(A)) dist(right(A))交换left(A) 和right(A) 最后由于right(A) 的距离可能发生改变我们必须更新A的距离 dist(A) ← dist(right(A)) 1 不难验证经这样合并后的树C符合性质1和性质2因此是一棵左偏树。至此左偏树的合并就完成了。 我们可以用下面的代码描述左偏树的合并过程 Function Merge(A, B) If A NULL Then return B If B NULL Then return A If key(B) key(A) Then swap(A, B) right(A) ← Merge(right(A), B) If dist(right(A)) dist(left(A)) Then swap(left(A), right(A)) If right(A) NULL Then dist(A) ← 0 Else dist(A) ← dist(right(A)) 1 return A End Function 下面我们来分析合并操作的时间复杂度。从上面的过程可以看出每一次递归合并的开始都需要分解其中一棵树总是把分解出的右子树参加下一步的合并。根据性质3一棵树的距离决定于其右子树的距离而右子树的距离在每次分解中递减因此每棵树A或B被分解的次数分别不会超过它们各自的距离。根据性质4分解的次数不会超过ëlog(N11)û ëlog(N21)û -2其中N1和N2分别为左偏树A和B的节点个数。因此合并操作最坏情况下的时间复杂度为O( ëlog(N11)û ëlog(N21)û -2) O(log N1 log N2)。 3.2 插入新节点 单节点的树一定是左偏树因此向左偏树插入一个节点可以看作是对两棵左偏树的合并。下面是插入新节点的代码 Procedure Insert(x, A) B ← MakeIntoTree(x) A ← Merge(A, B) End Procedure 由于合并的其中一棵树只有一个节点因此插入新节点操作的时间复杂度是O(logn)。 3.3 删除最小节点 由性质1我们知道左偏树的根节点是最小节点。在删除根节点后剩下的两棵子树都是左偏树需要把他们合并。删除最小节点操作的代码也非常简单 Function DeleteMin(A) t ← key(root(A)) A ← Merge(left(A), right(A)) return t End Function 由于删除最小节点后只需进行一次合并因此删除最小节点的时间复杂度也为O(logn)。 3.4 左偏树的构建 将n个节点构建成一棵左偏树这也是一个常用的操作。 算法一 暴力算法——逐个节点插入时间复杂度为O(nlogn)。 算法二 仿照二叉堆的构建算法我们可以得到下面这种算法 Ø 将n个节点每个节点作为一棵左偏树放入先进先出队列。 Ø 不断地从队首取出两棵左偏树将它们合并之后加入队尾。 Ø 当队列中只剩下一棵左偏树时算法结束。 下面分析算法二的时间复杂度。假设n2k则 前 次和并的是两棵只有1个节点的左偏树。 接下来的 次合并的是两棵有2个节点的左偏树。 接下来的 次合并的是两棵有4个节点的左偏树。 …… 接下来的 次合并的是两棵有2i-1个节点的左偏树。 合并两棵2i个节点的左偏树时间复杂度为O(i)因此算法二的总时间复杂度为 。 3.5 删除任意已知节点 接下来是关于删除任意已知节点的操作。之所以强调“已知”是因为这里所说的任意节点并不是根据它的键值找出来的左偏树本身除了可以迅速找到最小节点外不能有效的搜索指定键值的节点。故此我们不能要求请删除所有键值为100的节点。 前面说过优先队列是一种容器。对于通常的容器来说一旦节点被放进去以后容器就完全拥有了这个节点每个容器中的节点具有唯一的对象掌握它的拥有权ownership。对于这种容器的应用优先队列只能删除最小节点因为你根本无从知道它的其它节点是什么。 但是优先队列除了作为一种容器外还有另一个作用就是可以找到最小节点。很多应用是针对这个功能的它们并没有将拥有权完全转移给优先队列而是把优先队列作为一个最小节点的选择器从一堆节点中依次将它们选出来。这样一来节点的拥有权就可能同时被其它对象掌握。也就是说某个节点虽不是最小节点不能从优先队列那里“已知”但却可以从其它的拥有者那里“已知”。 这种优先队列的应用也是很常见的。设想我们有一个闹钟它可以记录很多个响铃时间不过由于时间是线性的铃只能一个个按先后次序响优先队列就很适合用来作这样的挑选。另一方面使用者应该可以随时取消一个“已知”的响铃时间这就需要进行任意已知节点的删除操作了。 我们的这种删除操作需要指定被删除的节点这和原来的删除根节点的操作是兼容的因为根节点肯定是已知的。上面已经提过在删除一个节点以后将会剩下它的两棵子树它们都是左偏树我们先把它们合并成一棵新的左偏树。 p ← Merge(left(x), right(x)) 现在p指向了这颗新的左偏树如果我们删除的是根节点此时任务已经完成了。不过如果被删除节点x不是根节点就有点麻烦了。这时p指向的新树的距离有可能比原来x的距离要大或小这势必有可能影响原来x的父节点q的距离因为q现在成为新树p的父节点了。于是就要仿照合并操作里面的做法对q的左右子树作出调整并更新q的距离。这一过程引起了连锁反应我们要顺着q的父节点链一直往上进行调整。新树p的距离为dist(p)如果dist(p)1等于q的原有距离dist(q)那么不管p是q的左子树还是右子树我们都不需要对q进行任何调整此时删除操作也就完成了。 如果dist(p)1小于q的原有距离dist(q)那么q的距离必须调整为dist(p)1而且如果p是左子树的话说明q的左子树距离比右子树小必须交换子树。由于q的距离减少了所以q的父节点也要做出同样的处理。 剩下就是另外一种情况了那就是p的距离增大了使得dist(p)1大于q的原有距离dist(q)。在这种情况下如果p是左子树那么q的距离不会改变此时删除操作也可以结束了。如果p是右子树这时有两种可能一种是p的距离仍小于等于q的左子树距离这时我们直接调整q的距离就行了另一种是p的距离大于q的左子树距离这时我们需要交换q的左右子树并调整q的距离交换完了以后q的右子树是原来的左子树它的距离加1只能等于或大于q的原有距离如果等于成立删除操作可以结束了否则q的距离将增大我们还要对q的父节点做出相同的处理。 删除任意已知节点操作的代码如下 Procedure Delete(x) q ← parent(x) p ← Merge(left(x), right(x)) parent(p) ← q If q ≠ NULL and left(q) x Then left(q) ← p If q ≠ NULL and right(q) x Then right(q) ← p While q ≠ NULL Do If dist(left(q)) dist(right(q)) Then swap(left(q), right(q)) If dist(right(q))1 dist(q) Then Exit Procedure dist(q) ← dist(right(q))1 p ← q q ← parent(q) End While End Procedure 下面分两种情况讨论删除操作的时间复杂度。 情况1p的距离减小了。在这种情况下由于q的距离只能缩小当循环结束时要么根节点处理完了q为空要么p是q的右子树并且dist(p)1dist(q)如果dist(p)1dist(q)那么p一定是q的左子树否则会出现q的右子树距离缩小了但是加1以后却大于q的距离的情况不符合左偏树的性质3。不论哪种情况删除操作都可以结束了。注意到每一次循环p的距离都会加1而在循环体内dist(p)1最终将成为某个节点的距离。根据性质4任何的距离都不会超过logn所以循环体的执行次数不会超过logn。 情况2p的距离增大了。在这种情况下我们将必然一直从右子树向上调整直至q为空或p是q的左子树时停止。一直从右子树升上来这个事实说明了循环的次数不会超过logn性质4。 最后我们看到这样一个事实就是这两种情况只会发生其中一个。如果某种情况的调整结束后我们已经知道要么q为空要么dist(p)1 dist(q)要么p是q的左子树。这三种情况都不会导致另一情况发生。直观上来讲如果合并后的新子树导致了父节点的一系列距离调整的话要么就一直是往小调整要么是一直往大调整不会出现交替的情况。 我们已经知道合并出新子树p的复杂度是O(logn)向上调整距离的复杂度也是O(logn)故删除操作的最坏情况的时间复杂度是O(logn)。如果左偏树非常倾斜实际应用情况下要比这个快得多。 3.6 小结 本章介绍了左偏树的各种操作我们可以看到左偏树作为可并堆的实现它的各种操作性能都十分优秀且编程复杂度比较低可以说是一个“性价比”十分高的数据结构。左偏树之所以是很好的可并堆实现是因为它能够捕捉到具有堆性质的二叉树里面的一些其它有用信息没有将这些信息浪费掉。根据堆性质我们知道从根节点向下到任何一个外节点的路径都是有序的。存在越长的路径说明树的整体有序性越强与平衡树不同平衡树根本不允许有很长的路径左偏树尽大约一半的可能保留了这个长度并将它甩向左侧利用它来缩短节点的距离以提高性能。这里我们不进行严格的讨论左偏树作为一个例子大致告诉我们放弃已有的信息意味着算法性能上的牺牲。下面是最好的左偏树有序表插入操作是按逆序发生的自然的有序性被保留了和最坏的左偏树平衡树插入操作是按正序发生的自然的有序性完全被放弃了。 以上是关于左偏树的定义与性质,结合HDU1512,撰写代码如下: #include iostreamusing namespace std; typedef struct { long dis; long key; long l,r; }node;const long MAXN100010; node hash[MAXN];long father[MAXN];long n; inline void init() { long i; for (i1;in;i) { scanf(%ld,hash[i].key); hash[i].dishash[i].lhash[i].r0; father[i]i; } } inline long Merge(long A,long B) { if (A0) { return B; } if (B0) { return A; } if (hash[B].keyhash[A].key) { swap(A,B); } hash[A].rMerge(hash[A].r,B); father[hash[A].r]A; if (hash[hash[A].r].dishash[hash[A].l].dis) { swap(hash[A].r,hash[A].l); } if (hash[A].r0) { hash[A].dis0; } else { hash[A].dishash[hash[A].r].dis1; } return A; } inline long getRoot(long pos) { while (father[pos]!pos) { posfather[pos]; } return pos; } inline long pop(long fx) { long l,r; lhash[fx].l; rhash[fx].r; father[l]l; father[r]r; hash[fx].dishash[fx].lhash[fx].r0; return Merge(l,r); } inline long push(long top,long fx) { return Merge(top,fx); } inline void Solove() { long m,i; scanf(%ld,m); for (i0;im;i) { long from,to; scanf(%ld %ld,from,to); long fx,fy; fxgetRoot(from); fygetRoot(to); if (fxfy) { printf(-1\n); } else { long top; hash[fx].keyhash[fx].key/2; toppop(fx); frompush(top,fx); hash[fy].keyhash[fy].key/2; toppop(fy); topush(top,fy); long lmaxpush(from,to); printf(%ld\n,hash[lmax].key); } } }int main() { while (scanf(%ld,n)!EOF) { init(); Solove(); } return 0; } 转载于:https://www.cnblogs.com/zhuangli/archive/2008/08/22/1273876.html
