网站怎样改logo,openshift安装wordpress密码忘记,自己做免费网站吗,倒v是网站设置的还是作家自己1.算法
作为完全二叉堆的一个应用#xff0c;这节来介绍堆排序算法。
是的#xff0c;谈到优先级队列#xff0c;我们很自然地就会联想到排序。因为就其功能而言#xff0c;包括完全二叉堆在内的任何一种优先级队列都天生地具有选取功能#xff0c;也就是选取其中的最大…1.算法
作为完全二叉堆的一个应用这节来介绍堆排序算法。
是的谈到优先级队列我们很自然地就会联想到排序。因为就其功能而言包括完全二叉堆在内的任何一种优先级队列都天生地具有选取功能也就是选取其中的最大元。因此很自然地就会联想起选择排序。
还记得这样一幅插图上图中右上图我们曾经用它来解释选择排序的原理及过程。不妨温习一下在选择排序算法中我们始终将整个序列分为两部分也就是左侧的待排序部分以及右侧的已排序部分。而且前者中的任何一个元素都不大于后者中的任何一个元素。因此我们只需反复地遍历待排序元素从中选取出最大者并将它加入到已排序的子序列中。是的正因为我们每次都需要对待排序的部分作遍历从而导致每次选取都需要线性的时间以致整个算法累计需要平方量级的时间。
究其原因可以理解为我们当初对数据结构的理解和掌握还非常有限以至于我们只能借助简单的数据结构来组织待排序的元素。而经过了一段时间的学习之后我们已经今非昔比我们可以运用更为高级的数据结构来组织这些待排序的元素从而实现更高的选取效率。
比如联想到我们刚刚学过的内容很自然地就会想到用一个完全二叉堆来取代此前简单的线性结构。如果暂时忽略底层的具体实现我们就会发现整个算法流程可以基本保持不变。
此前在与预处理阶段对整个线性序列的初始化在这里则对应于建堆操作。我们刚刚介绍过如果采用 Floyd 算法这一步只需线性的时间。接下来我们需要反复地取出最大元也就是整个堆当前的堆顶。我们知道 delMax操作每次只需 log n 的时间。没错log n 而不再是 n。因此整个算法的复杂度也就应该是 n log n而不再是 n 2 n^2 n2。
当然此前的不变性依然保持也就是待排序的部分始终都不超过已排序部分因此算法的正确性依然可以得到保证。那么难道这个算法就是这样的平淡无奇不是的事实上堆排序的奥妙还不止于此比如在空间复杂度方面堆排序算法还可以做得更好。
2.就地 准确地讲在空间复杂度方面我们希望堆排序算法能够做到就地也就是除了输入数据以外只需要常数的辅助空间。 这种构思是有可能实现的因为我们注意到所谓的完全二叉堆在物理上就是不折不扣的向量。
因此我们或许可以令完全二叉堆与已排序的部分在同一个向量中和平共处经过精巧的设计我们的确可以将这一构想兑现为这种形式具体来说已排序部分依然居于向量的后端而与之互补的前缀则恰好构成一个完全二叉堆如果沿用大顶堆的惯例我们可以立即发现堆中的最大元必然始终都是0号元素而接下来需要与之兑换的 X则必然是相对于已排序元素而言秩为 -1 的那个元素。
按照以上堆排序的初始版本我们首先需要取出这个最大的元素然后用 x 来取而代之然后再将备份的最大元植入 x 这个位置。当然为了算法能够继续持续下去我们还需要对新的根节点做下滤调整。
对于这样的连续4步操作你能发现有什么可以优化的地方吗 是的这里的1、2、3完全可以整合起来只需 m 和 x 之间的一次兑换即可等效地完成。因此算法过程中的每一步迭代可以进一步的规整为两大步骤也就是第一步交换以及第二步下滤。是的反复地交换下滤交换下滤。直至堆变空。在整个算法的过程中除了交需要用到常数个辅助空间之外我们并不需要任何更多的辅助空间。
以上过程可以描述为这样的伪代码上图最下面行但是它又如何进一步地实现为真正的代码呢
3.实现 在这里给出堆排序的一个更为通用的算法版本也就是说对于任何的向量这个算法都可以对其中任意指定的区间进行排序。
作为初始化首先需要调用完成二叉堆的建堆算法在线性的时间内将向量的这个区间整理为一个完全二叉堆。此后进入反复迭代请留意这个迭代所具有的不变性也就是完全二叉堆当前所在的区间是由 lo 和 hi 界定的按照我们一直以来采用的惯例lo 所对应的是堆的首元素而 hi 所指示的则是这个堆尾部的哨兵。
因此在每一步迭代中我们都只需取出首元素位置处的最大元并且将它与末元素交换而新的堆顶元素的下滤功能则同样是由 delMax 在底层完成。
4.实例 看堆排序算法的一个具体实例考察这样一个规模为 5 的向量首先从逻辑上将它视作为一棵完全二叉树其中有两个内部节点也就是2和4于是我们采用 Floyd 算法分别对 2 和 4分别做一趟下滤即可最终得到这样一个完全二叉堆。至此也就完成了算法的预处理步骤。 接下来我们进入算法的主体循环请注意在一开始整个向量都是未排序的部分而已排序的部分初始为空。即便如此我们依然可以使用算法的基本策略也就是令当前的堆顶与末元素互换位置。 破坏之后的瞬间应该是这样上图上左二。原来的末元素2成为了堆顶而5则在逻辑上从原来的堆中分离出来加入原本为空的 S。也就是说已排序的序列此时已经拥有了第一个元素。 当然我们还需要对新的堆顶做下滤调整从而使得剩下的 4 个元素依然恢复为一个堆尽管规模减少了一个单位。不出意外接下来的最大元 4 也自然成为了新的堆顶上图上左三。 因此在下一轮迭代中我们依然是将这个新的堆顶与当前的末元素互换位置在逻辑上这等效于将堆顶摘出并归入到有序序列中上图下左一。 同样我们仍需对新的根节点做一次下滤调整从而使得剩余的三个元素能够继续保持为是一个合法的大顶堆上图下左三。 不出预料当前尚未排序的元素中的最大者 3 此时也必然就是堆顶。因此,我们也只需令它与当前的末元素 2 做一次兑换。在逻辑上这依然等同于将这个堆顶摘出并归入到有序列中。 此后再经过一轮下滤调整剩余的元素也依然会恢复为一个合法的大顶堆尽管此时已经只剩最后的两个元素了。
