本文共 3775 字,大约阅读时间需要 12 分钟。
第十章:优先级队列
需求与动机
基本实现
使用向量实现复杂度偏高
使用有序向量尽管获得和删除最大元素很快,多少插入操作却仍要线性的时间。
列表和有序列表也均不呢高效的实现所有的接口。
而采用BBST实现优先级队列,功能太过复杂,PQ只需维护偏序关系即可,需要一种各类操作复杂度都不超过logn的数据结构。
完全二叉堆:结构
完全二叉堆在逻辑上等同于完全二叉树,物理上借助向量实现。
即按二叉树的层次遍历序列存于向量中,由于向量的秩从0开始,所以可以得到秩为i的节点,父节点在(i-1)>>1的位置,两个孩子节点分别在2i + 1及2i + 2的位置。
内部节点即非叶节点,设有x个叶子节点,度为0,按照之前的推论应该有x – 1个度为2的节点,并且由于是完全二叉树,度为1的节点最多有1个,故n为奇数时,n = 2x,即向量的后半部分都是叶子节点,内部节点的最大秩为n / 2 – 1;n为偶数时,n = 2x – 1,此时没有度为1的节点,内部节点的最大秩为n / 2 – 1。故内部节点的最大秩始终为n / 2 – 1.
完全二叉堆类同时继承了优先级队列类和向量类,同时具备向量的所有接口以及优先级队列的三个接口。
完全二叉堆只需要满足堆序性即可,即每个节点都不小于其孩子节点,故根节点就是最大的元素。
完全二叉树:插入与上滤
插入元素e,只需要将e作为末元素接入向量,然后与其父结点比较大小,大于其父节点则与其父节点交换位置(上滤),直至满足堆序性为止。
这里一般情况下交换两个节点的值需要3次操作,如果先将待插入节点的值保存下来,每次交换实际上仅仅对父节点下移,直至找到最终的位置才将e赋给它,这样可以将常系数的3降低为1.
完全二叉堆:删除与下滤
完全二叉堆的删除操作只需删除堆顶元素,采取的策略是用最末端的元素取代堆顶元素,然后与其孩子节点中较大者交换,不断下滤,直至恢复堆序性。
完全二叉堆:批量建堆
给定n个数,要求建成完全二叉堆,很容易想到的就是从第一个元素开始,对每个元素调用插入函数逐个插入。
按照n个元素的顺序逐个插入,在向量中自左向右的插入每个元素相当于在堆中自上而下,自左而右的插入每个元素,而插入操作是一次次的上滤,故该算法可以看做是自上而下的上滤。
最坏情况下,每个元素都要上滤至根,其成本正比于节点的深度,对于底层n / 2个的叶节点而言,其深度均为O(logn),光是上滤叶子节点消耗的设计就已经是O(nlogn)级别的了。
已知两个堆以及一个节点,要将它们合并为一个堆,只需要先以该节点作为两个子堆的根,再不断下滤即可(类似于删除操作)。换而言之,要想建堆,也可以自下而上,自右而左的合并节点成为新的堆,直至所有节点都被合并成一个堆为止。这种自下而上的下滤算法实现如上图所示。
因为只有内部节点才需要下滤,所以可以从秩为n / 2 – 1的节点(最后一个内部节点)向前依次下滤。
以上图为例,算法开始先对最后的内部节点3实现下滤,得到以8为根的子堆,再对6下滤,得到以7位根的子堆,然后是对1下滤,得到以9为根的子堆,最后对2实行下滤,得到最后的堆。可以发现,每个内部节点下滤的成本正比于节点的高度。
考察满树n = 2^(d+1) – 1,d为树的高度,则高度为d的节点有1个,高度为d – 1的节点有2个,高度为d – i的节点有2^i个,…,高度为0的节点有2^d个。故所有节点的高度和为(d - i)* 2^i,i从0到d上求和,如上图所示,式子可以分解为d乘以2为公比的的等比数列和与一个等差乘等比的数列和相加。T(n) = 1*2+2*2^2 +…+ d*2^d;2T(n) = 1*2^2+2^2^3+…+(d-1)*2^d+d*2^(d+1).两式相减得-T(n)= 2 + 2^2 + 2^3 + … + 2^d – d*2^(d+1) = 2^(d+1) – 2 - d*2^(d+1).从而T(n) = (d – 1)*2^(d+1) + 2.按照上图的推导可得高度和=2^(d+1) – d – 2 = n – log2(n + 1) = O(n).
所以自下而上下滤算法的时间复杂度是线性的,至于为什么节点的高度和要小于深度和,是因为完全二叉堆上窄下宽,节点较多的深度高而高度低。
堆排序
在选择排序中,每次需要在左侧无序的序列中选出最大者加入到有序序列的最前面,可以用堆来维护无序序列,使得每次获得最大元素的操作在O(logn)时间内完成。
可以进一步的实现就地堆排序算法,即首先将无序序列批量建堆,然后取秩为0的元素与有序序列的前一个元素交换,接着对堆实行下滤恢复堆序性,重复该操作直至序列整体有序。
堆排序的优点在于不需额外的空间,并且不需要全排序即可找出前k个词条。另外由于每次都是将无序序列后面的元素插入到堆顶,会导致算法的不稳定性,如果需要解决该问题,可修改下滤接口,使得孩子节点只要不小于父节点,父节点就要下滤,且优先考虑和右孩子交换。
锦标赛排序
可见,锦标赛树是将叶子节点中的较小者作为根来连接叶子节点,并逐步比较至根。所有的内部节点都是与兄弟节点比较的优胜者。
锦标赛树每个叶子节点都是选手,内部节点记录比赛的胜者(较小者),而败者树相反,父节点记录比赛中的失败者,然后胜者继续参与下一轮比赛,最后增设根节点的父节点来记录冠军。
败者树实际上是一棵完全二叉树,可以看做是胜者树的一种变体。败者树简化了重构,败者树的重构只是与该结点的父结点的记录有关,而胜者树的重构还与该结点的兄弟结点有关。
对于锦标赛树而言,重构时首先需要和兄弟节点比较确定胜者,然后才能和父节点比较看看胜者有没有更新,这里如果是更新了之前的胜者,比如把上图左边的29更新为30,然后固然可以不和父节点比较直接更新父节点,然后继续和兄弟节点比较。但是在此之前我们不知道叶子节点30在更新前是否是胜者,就算是更新了败者52为30,29依然比它小,依然要作为父节点,此刻如果不和父节点29比较就不知道不需要更新,从而还需要和上层节点比较,但是每次更新后,孩子中的胜者如果和父节点进行比较判等下,不等则更新父节点并考察上次节点,相等则不必继续更新上层了。这样,为了更新父节点,更新的节点需要先和兄弟节点比较再和父节点比较,需要比较两次。而败者树只需要和父节点比较,因此简化了重构。
多叉堆
左式堆:结构
如果要实现将两个堆合并,将较小规模的堆一个个插入较大规模的堆,复杂度是O(mlog(n+m)),如果仿照批量建堆算法合并两个堆,时间复杂度是O(m + n),但是与批量建堆不同的是,这里的A和B各自已经满足了堆序性,批量建堆没有利用该性质。
引入空节点路径长度(npl)的概念,首先添加外部节点转化为真二叉树。定义所有外部节点的npl值为0,其他节点的npl(x) = 1 + min(npl(lc(x)),npl(rc(x))),即左右子树中nol值较小者+1,如果将这里的min换成max便是节点高度的递推式了。直观上说,npl是节点到外部节点的最近距离,也是以该结点为根的最大满子树的高度。
左倾:任何内部节点x的左孩子的npl不超过右孩子的npl,这意味着,任何节点的npl都等于右孩子的npl + 1.满足左倾性的堆称为左式堆。
左式堆:合并
由于左式堆结构上不再是完全二叉树,所以不能使用向量实现,这里使用二叉树实现左式堆。
合并算法:要合并左式堆a和b,需要先比较根节点a和b大小,如果b大则交换下位置,当a>b时,取a的右孩子与b合并后作为a的右子树,并且判断此时a左孩子的npl是否是不大于右孩子的npl,大于则交换左右子树。
如上图所示,要合并分别以17和15根的堆,首先判断17 > 15,遂问题转化为17的右孩子12与以15为根的堆合并的问题,15 > 12,问题转化为15的右孩子8与12合并的问题,12 > 8,故将8作为12的右孩子接入,同时由于此时12的左倾性不满足,交换左右孩子位置,使得8成为12的左孩子,然后将以12为根的子树接入到 15的右孩子,再判断左倾性是否满足,以此类推。
左式堆的合并操作的时间复杂度正比于右侧链的长度,即O(logn)。
左式堆:插入与删除
左式堆的插入操作可以将待插入的节点视为高度为0的堆,直接调用合并算法即可完成。
左式堆的删除操作同样只需要先删除堆顶元素,然后调用合并算法将左右子树合并即可。与插入操作一样,删除操作的时间复杂度为O(logn)。
AVL树合并算法:
条件:T1中所有节点都不大于T2中节点,T1的高度大于T2.
算法:取T2中最小的节点m,m必然是叶子节点,此时,对T2而言相当于删除了m,T2删除m后的子树记为T2’,其高度至多下降1.同时在T1的最右侧通路上必然可以找到一棵子树,以p为根,高度不小于T2’,且至多比T2’高一层,以m为根结点,将以p为根的子树和T2’分别作为左右孩子合并成新的AVL树。再将以m为树根的子树作为p父节点的右孩子接入,此刻唯一也可能失衡的节点即m的父节点,旋转调整直至恢复平衡即可。
旋转调整的时间复杂度为O(H1 – H2),总的时间复杂度为O(max(H1,H2))。
转载地址:https://blog.csdn.net/qq_30277239/article/details/103188589 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!