定州网站建设【定州网络公司】定州做网站、定州微信公众号开发、定州网站设计、定州小程序制作

发表日期： 2021-04-13 11:29:19 浏览次数：92

定州市，河北省辖县级市，由保定市代管， [1] 是河北省省直管县（市）体制改革试点县（省直管县行政区划隶属关系不变 [2] ）， [3-4] 是全省重点培育的新兴区域中心城市。连续4年获评全国中小城市投资潜力百强、新型城镇化质量百强，晋级全国科技创新百强，入围全国县域经济强县。面积1283平方公里，截至2019年，定州市常住总人口123.09万人，辖25个乡镇（办），542个村（社区）。 [5-6]

定州市位于京津冀经济区，是京津冀经济区重要节点城市 [7] ，国家新型城镇化综合试点地区 [8] ，河北省十二五规划重点培育的现代化中等城市 [9] ，河北省十大历史文化名城之一。

2019年，定州市户籍总户数37.3万户，户籍总人口124.1万人，比上年增加0.3万人。常住总人口123.09万人，比上年末增加0.4万人。 [6] 2019年，定州市生产总值实现3330429万元，比上年增长7.1%。按常住人口计算，定州市人均地区生产总值为27101元。 [6] 2020年9月，入选河北省食品产业强县（市、区）（培育型）名单。 [10] 2020年12月，入选河北省数字乡村试点地区名单。

5.9.5　习题

1. 考虑图5-45中的堆，说明在下列情况下分别会发生什么。

(a) 插入3

(b) 插入20

(d) 再次删除最大元素

2. 通过对i 的归纳证明(5.2)式。

3. 通过对违背偏序树属性的节点的深度进行归纳，证明图5-46中的bubbleUp函数可以正确地将有一处违背偏序树属性的树还原为具有偏序树属性的树。

4. 证明：如果A之前是大小为n-1的堆，那么insert(A,x,n)函数可以使A变为大小为n 的堆。

5. 通过对违背偏序树属性的节点的高度进行归纳，证明图5-48中的bubbleDown函数可以正确地将有一处违背偏序树属性的树还原为具有偏序树属性的树。

6. 证明：deletemax(A,n)可以让大小为n 的堆变为大小为n-1的堆。如果A之前不是堆，会发生什么？

7. 证明：bubbleDown(A,1,n)处理长度为n 的堆所花时间是O(logn)。

8. ** 随机选出不同优先级的n 个元素构成堆，该堆是偏序树的概率是多少？如果没法总结出一般规则，就编写递归函数计算这一表示为n 的函数的概率。

9. 实现偏序树不一定要使用堆。假设使用之前用于二叉树的常规的左子节点右子节点数据结构。展示如何使用这一结构实现bubbleDown、insert和deletemax函数。

10. * 二叉查找树也可以用作优先级队列的抽象实现。展示如何使用具有左子节点右子节点数据结构的二叉查找树实现插入和deletemax操作。这些操作在最坏情况下以及在一般情况下的运行时间分别是多少？

5.10　堆排序：利用平衡偏序树排序

现在要介绍被称为堆排序的算法。它会分两个阶段为数组A[1..n]排序。在第一个阶段，堆排序会给A 偏序树属性。堆排序的第二个阶段会反复从堆中选出剩余元素中的最大元素，直到堆只由最小的元素构成，这样就完成了对数组A 的排序。

图 5-50　堆排序过程中数组A 的情况

图5-50展示了处于第二阶段的数组A。数组的开头部分具有偏序树属性，而剩下的部分则是以非递减次序排好序的元素。此外，已排序部分是数组中前n-i大的元素。在第二阶段，i的值可以从n减到1，从而让一开始为整个数组A的堆，最终减少到只剩下位于A[1]的最小元素。更详细地讲，第二阶段由如下步骤组成。

1. 将A[1..i]中最大元素A[1]与A[i ]交换。因为A[i+1..n]中所有元素都不小于A[1..i]中的元素，而且我们刚刚将A[1..i]中最大的元素移动到了位置i，所以可知A[i..n]是数组中前n-i-1大的元素，而且已经是排好次序的。

2. i 的值是递减的，每次将堆的大小减少1。

3. 通过下压根节点处的元素（就是刚移动到A[1]的元素），还原开头部分的偏序树属性。

示例 5.32

考虑图5-45中的数组，它是具有偏序树属性的。这里从第二阶段的第一次迭代开始分析。在第一步中，要将A[1]与A[10]交换，得到：

第二步是将堆的大小减小为9，而第三步则是通过调用bubbleDown(1)还原前9个元素的偏序树属性。在这次调用中，A[1]和A[2]进行了交换。

接着，A[2]与A[4]进行了交换。

最后，A[4]和A[9]交换：

至此，A[1..9]具有了偏序树属性。

第二阶段的第二次迭代首先要交换A[1]中的元素18与A[9]中的元素5。在将5往下压到合适位置后，数组就成了

到这里，数组中最后两个元素已经是最大的两个元素，而且是已经排好次序的。

第二阶段会不断继续，直到完成对数组的排序。

5.10.1　数组的堆化

可以非正式地将堆排序描述为：

for (i = 1; i <= n; i++)
　　insert (ai );
for (i = 1; i <= n; i++)
　　deletemax

要实现这一算法，先将待排序的n 个元素a1、a2、…、an插入一个最初为空的堆中。然后执行n 次deletemax操作，按从大到小的次序取出元素。图5-50所示的安排让我们可以随着数组中堆部分的萎缩，在数组的尾部存储已删除的元素。

我们已经在5.9节中论证过插入和deletemax操作的运行时间都是O(logn)，而且每种操作显然都要执行n 次，所以这是一种可与归并排序媲美的O(n logn)排序算法。其实，在只需要最大的几个元素，而不需要整个已排序表的情况下，堆排序还能优于归并排序。原因在于，要让数组变成堆，如果使用图5-51所示的heapify函数，只需要O(n)的时间就能完成，而不是O(n logn)。

void heapify(int A[], int n){
    int i;

    for (i = n/2; i >= 1; i--)
        bubbleDown(A, i, n);}复制代码

图 5-51　数组的堆化

5.10.2　`Heapify`的运行时间

首先，图5-51中对bubbleDown的n/2次调用总时间看起来应该是O(n logn)，因为我们了解的bubbleDown运行时间上界只有logn 这一个。不过，如果利用向下压元素的序列大多非常短这一事实，就可以得到更紧的边界——O(n)。

一开始，甚至都不必堆数组的后半部分调用bubbleDown，因为那里的节点全部是叶子节点。如果数组的第二个四分之一部分——也就是A[(n/4)+1..n/2]——中的元素存在比它们的子节点小的，就可以调用bubbleDown一次。不过，它们的子节点是在数组后半部分，都是叶子节点，因此，在A 的第二个四分之一中，最多调用一次bubbleDown。同样，在数组的第二个八分之一中，最多调用两次bubbleDown。在数组个区域中调用bubbleDown的次数如图5-52所示。

{%}

图 5-52　随着数组下标不断变大，对bubbleDown的调用次数迅速减少

现在来计算一下heapify调用了多少次bubbleDown，其中包括递归调用。从图5-52可看出，可以将A分为若干个区段，其中第i 个区段是由大于n/2i+1且不大于n/2i 的 j 对应的A[j]组成。因此，区段i 中的元素数就是n/2i+1，而且区段i 中每个元素至多调用i 次bubbleDown。此外，i>log2n 的区段都为空，因为它们至多包含n/21+log2n=1/2个元素。A[1]是区段log2n 中唯一的元素，因此需要计算和值

$\sum^{\log_2n}_{i=1}in/2^{i+1}$ 　　　　　　(5.3)

将(5.3)的有限和扩展为无限和，并提取出因式n/2，就可以给出该和值的上界

$\frac{n}{2}\sum^{\infty}_{i=1}i/2^i$

现在必须得出(5.4)式中和值的上界。 $\sum^{\infty}_{i=1}i/2^i$ 可以写为

(1/2)+(1/4+1/4)+(1/8+1/8+1/8)+(1/16+1/16+1/16+1/16)+…

可以将这些2的乘方的倒数写为如图5-53所示的三角形。每一行都是公比为1/2的无穷几何级数，而其和则是级数中第一项的两倍，正如图5-33右侧所示。各行之和又形成了另一个几何级数，而它的和是2。

$\begin{align*}1/2+1/4+1/8+1/16+\cdots&=1\\1/4+1/8+1/16+\cdots&=1/2\\1/8+1/16+\cdots&=1/4\\1/16+\cdots&=1/8\\\cdots&=\cdots\end{align*}$

图 5-53　将 $\sum^{\infty}_{i=1}i/2^i$ 排列为三角和

这样一来，(5.4)的上界为(n/2)×2=n。也就是说，在函数heapify中调用bubbleDown的次数不超过n。因为已经得出每次调用花费的时间为O(1)，不含任何递归调用，所以可以得出结论：heapify花的总时间为O(n)。

5.10.3　完整的堆排序算法

堆排序C语言程序如图5-54所示。它使用整数数组A[1..MAX]表示堆。待排序的元素被插入A[1..n]中。图5-54中函数声明的定义包含在5.9节和5.10节中。

     #include <stdio.h>

     #define MAX 100

     int A[MAX+1];

     void bubbleDown(int A[], int i, int n);
     void deletemax(int A[], int *pn);
     void heapify(int A[], int n);
     void heapsort(int A[], int n);
     void swap(int A[], int i, int j);

     main()
     {
         int i, n, x;

         n = 0;
         while (n < MAX && scanf("%d", &x) != EOF)
             A[++n] = x;
         heapsort(A, n);
         for (i = 1; i <= n; i++)
             printf("%d\n", A[i]);
     }

     void heapsort(int A[], int n)
     {
         int i;(1)      heapify(A, n);(2)      i = n;(3)      while (i > 1)(4)          deletemax(A, &i);
     }复制代码

图 5-54　对数组进行堆排序

第(1)行调用heapify，它将待排序的n个元素变成一个堆。第(2)行将标记堆尾的i初始化为n。第(3)和第(4)行的循环将deletemax应用n-1次。我们应该重新审视图5-49中的代码，会看到deletemax(A,i)会将当前堆中最大的元素（永远是A[1]）与A[i ]交换。这样一来，i 每次会减少1，所以堆的大小也会缩小1。在第(4)行被deletemax“删除”的元素现在成为数列已排序尾部的一部分。它不大于之前的尾部A[i+1..n]中的任何元素，而不小于仍在堆中的任意元素。因此，声明的属性得到保持，堆中的所有元素都先于尾部的所有元素。

5.10.4　堆排序的运行时间

刚刚已经确定了第(1)行中的heapify函数花的时间与n 成比例。第(2)行显然花了O(1)的时间。因为第(3)行和第(4)行的循环每进行一次，i 就减少1，所以循环要进行n-1次。第(4)行中对deletemax的调用花的时间是O(logn)。因此，整个循环的总运行时间为O(n logn)。这一时间主导了第(1)行和第(2)行的运行时间，所以heapsort函数处理n 个元素的运行时间是O(n logn)。

5.10.5　习题

1. 对3、1、4、1、5、9、2、6、5这列元素应用堆排序。

2. * 给出一个运行时间是O(n)的算法，使其从具有n个元素的表中找出前 $\sqrt{n}$ 大的元素。

5.11　小结

读者应该从本章中获取如下要点。

树是一种用于表示层次化信息的重要数据模型。
多种涉及数组和指针结合的数据结构可用于实现树，选择何种数据结构取决于要对树进行哪种操作。
树节点最重要的两种表示分别是最左子节点右兄弟节点表示和单词查找树（指向子节点的指针数组）。
递归算法和证明也适用于树。结构归纳法是普通归纳模式的一种变形，可以有效地对树中的节点数进行完全归纳。
二叉树是树模型的一种变形，它的每个节点最多可以有左子节点和右子节点。
二叉查找树是带标号的二叉树，它具有“二叉查找树属性”，即节点左子树的所有标号都先于该节点的标号，而且节点右子树的所有标号都后于该节点的标号。
词典抽象数据类型是可以对其执行插入、删除和查找操作的集合。二叉查找树可以有效地实现词典。
优先级队列是另一种抽象数据类型，是可以对其执行插入和deletemax操作的集合。
偏序树是种带标号的二叉树，它具有任意节点的标号都不小于其子节点标号的属性。
平衡偏序树除最下层之外的各层都被节点占满，而最下层只有靠左侧的位置被占据，它可以通过被称为堆的数组结构实现。这一结构提供了一种复杂度为O(logn)的优先级队列实现，并带来了一种复杂度为O(n logn)的排序算法——堆排序。