张北400电话办理【张北网站公司】张北百度优化、张北域名注册、张北网店美工、张北微信公众号托管

张北400电话办理【张北网站公司】张北百度优化、张北域名注册、张北网店美工、张北微信公众号托管

河北省张家口市张北县地处河北省西北部，内蒙古高原南缘的坝上地区，境域东西109公里，南北67公里，东南部与崇礼区交界，桦皮岭为全县最高点，海拔2128米；北、中部地势平坦，向西北渐低，安固里淖为最低点，海拔1300米。全县总面积4185平方公里，辖18个乡镇、366个行政村、1167个自然村，总人口37.2万人。居民以汉族为主，占总人口的98%，还有蒙古族、回族、满族等。张北县是离京津地区最近的高原地区，夏天气候凉爽是避暑胜地。

张北县被列为第一批国家新型城镇化综合试点地区。 [1]  2019年11月，入选第二批节水型社会建设达标县（区）名单。 [2]  2020年2月29日，退出贫困县序列，正式脱贫“摘帽”。 [3]  2020年12月，入选河北省数字乡村试点地区名单。

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 中唯一的元素，因此需要计算和值

　　　　　　(5.3)

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

现在必须得出(5.4)式中和值的上界。可以写为

(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。

图 5-53　将排列为三角和

这样一来，(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个元素的表中找出前大的元素。

5.11　小结

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

• 树是一种用于表示层次化信息的重要数据模型。

• 多种涉及数组和指针结合的数据结构可用于实现树，选择何种数据结构取决于要对树进行哪种操作。

• 树节点最重要的两种表示分别是最左子节点右兄弟节点表示和单词查找树（指向子节点的指针数组）。

• 递归算法和证明也适用于树。结构归纳法是普通归纳模式的一种变形，可以有效地对树中的节点数进行完全归纳。

• 二叉树是树模型的一种变形，它的每个节点最多可以有左子节点和右子节点。

• 二叉查找树是带标号的二叉树，它具有“二叉查找树属性”，即节点左子树的所有标号都先于该节点的标号，而且节点右子树的所有标号都后于该节点的标号。

• 词典抽象数据类型是可以对其执行插入、删除和查找操作的集合。二叉查找树可以有效地实现词典。

• 优先级队列是另一种抽象数据类型，是可以对其执行插入和deletemax操作的集合。

• 偏序树是种带标号的二叉树，它具有任意节点的标号都不小于其子节点标号的属性。

• 平衡偏序树除最下层之外的各层都被节点占满，而最下层只有靠左侧的位置被占据，它可以通过被称为堆的数组结构实现。这一结构提供了一种复杂度为O(logn)的优先级队列实现，并带来了一种复杂度为O(n logn)的排序算法——堆排序。

张北400电话办理【张北网站公司】张北百度优化、张北域名注册、张北网店美工、张北微信公众号托管