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

定州市是河北省下辖的县级市，由保定市代管。 [1] 是河北省省直县（市）体制改革试点县（省直县行政区划隶属不变[2]）。 [3-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年，定州市地区生产总值达到万元，比上年增长7.1%。按常住人口计算，定州市人均地区生产总值为万元。 [6]2020年9月入选河北省食品工业强县（市、区）名单（培育型）。 [10]2020年12月，入选河北省数字农村试点地区名单。

5.9.5 练习

1. 考虑图 5-45 中的堆并描述在以下情况下会发生什么。

(a) 插入 3

(b) 插入 20

(c) 删除最大元素

(d) 再次删除最大元素

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

3.通过总结违反偏序树属性的节点的深度，证明图5-46中的函数可以正确地将违反偏序树属性的树恢复为具有偏序树属性的树。

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

5. 通过总结违反偏序树性质的节点的高度，证明图5-48中的函数可以正确地将违反偏序树性质的树恢复为具有以下性质的树：一棵部分有序的树。

6. 证明：(A,n) 可以将大小为 n 的堆变成大小为 n-1 的堆。如果 A 之前不是堆会怎样？

7. 证明：(A,1,n) 处理长度为 n 的堆需要 O(logn) 时间。

8. ** 随机选择n个不同优先级的元素组成堆。堆是偏序树的概率是多少？如果您无法推广到一般规则，请编写一个递归函数来计算该函数的概率，用 n 表示。

9. 没有必要使用堆来实现偏序树。假设使用先前用于二叉树的常规左子右子数据结构。展示如何使用该结构来实现 , 和 函数。

10. * 二叉搜索树也可以作为优先级队列的抽象实现。演示如何使用具有左子右子数据结构的二叉搜索树实现插入和操作。这些操作的最坏情况和典型运行时间是多少？

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

现在我们将介绍称为堆排序的算法。它分两个阶段对数组 A[1..n] 进行排序。在第一阶段，堆排序会给 A 一个偏序树属性。堆排序的第二阶段会反复从堆中剩余的元素中选择最大的元素，直到堆中只剩下最小的元素，从而完成数组A的排序。

图5-50 数组A在堆排序时的情况

图5-50显示了第二阶段的阵列A。数组的开头具有部分有序树的属性，而数组的其余部分由按非降序排序的元素组成。另外，排序后的部分是数组中前ni个最大的元素。在第二阶段，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] 是数组中第一个 ni-1 最大元素，并且它已经排序。

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

3、通过压下根节点处的元素（即刚刚移动到A[1]的元素），恢复一开始的偏序树属性。

例5.32

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

第二步是将堆的大小减少到9，而第三步是通过调用(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 数组的堆化

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

对于 (i = 1; i