考研帮 > 数学 > 每日一练

7.8 序★4◎4

7.8 堆排序★4◎4

  设有n个元素的序列 k1,k2,…,kn,当且仅当满足下述关系之一时,称之为堆,如图7-1所示。

  

  若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点的值是最大(或最小)的。
  堆排序的基本思想:对于n个元素的表,首先将这n个元素按关键码建成堆,将堆顶元素输出,得到n个元素中关键码最小(或最大)的元素。然后,将剩下的n-1个元素建成堆,输出堆顶元素,得到n个元素中关键码次小(或次大)的元素。如此反复,便得到一个按关键码有序的序列,我们称这个过程为堆排序。
  因此,实现堆排序须解决两个问题:
  ① 如何将n个元素的序列按关键码建成堆。
  ② 输出堆顶元素后,怎样调整剩余n-1个元素,使其按关键码成为一个新堆。
  首先,讨论输出堆顶元素后,对剩余元素重新建成堆的调整过程。调整方法:设有m个元素的堆,输出堆顶元素后,剩下m-1个元素。将堆底元素送入堆顶,堆被破坏,其原因是根结点不满足堆的性质。将根结点与左、右子女中较小(或小大)的进行交换。若与左子女交换,则左子树堆被破坏,且左子树的根结点不满足堆的性质;若与右子女交换,则右子树堆被破坏,且右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成,如图7-2所示。这个自根结点到叶子结点的调整过程称为筛选。

  

  再讨论对n个元素初始建堆的过程,如图7-3所示。建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。n个结点的完全二叉树,最后一个结点是第 个结点的子女。对第个结点为根的子树进行筛选,使该子树成为堆;然后向前依次对以各结点为根的子树进行筛选,使之成为堆,直到根结点。
  堆排序:对n个元素的序列进行堆排序,先将其建成堆,以根结点与第n个结点交换;调整前n-1个结点成为堆,再以根结点与第n-1个结点交换;重复上述操作,直到整个序列有序。
  【效率分析】
  设树高为k,从根到叶的筛选,关键码比较次数最多为2(k-1)次,交换记录最多为k次。在堆建好后,排序过程的筛选次数,而建堆时的比较次数不超过4n次,因此堆排序最坏情况下,时间复杂度也为 。

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭