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次，因此堆排序最坏情况下，时间复杂度也为 。

985大学 211大学 全国院校对比 专升本 美国留学 留求艺网