C#数据结构与算法揭秘18

、堆排序

在直接选择排序中，顺序表是一个线性结构，要从有n个记录的顺序表中选择出一个最小的记录需要比较n-1 次。如能把待排序的n个记录构成一个完全二叉树结构，则每次选择出一个最大（或最小）的记录比较的次数就是完全二叉树的高度， 即log2n次， 则排序算法的时间复杂度就是O （nlog2n） 。 这就是堆排序(Heap Sort)的基本思想。
堆分为最大堆和最小堆两种。最大堆的定义如下：
设顺序表sqList中存放了n个记录， 对于任意的i(0≤i≤n-1)， 如果2i+1 n时有 sqList[i]的关键码不小于 sqList[2i+1]的关键码；如果 2i+2 n 时有sqList[i] 的关键码不小于 sqList[2i+2] 的关键码，则这样的堆为最大堆。 如果把这 n 个记录看作是一棵完全二叉树的结点，则 sqList[0]对应完全二叉树的根， sqList[1]对应树根的左孩子结点， sqList[2]对应树根的右孩子结点， sqList[3]对应 sqList[1]的左孩子结点，sqList[4]对应 sqList[2]的右孩子结点，如此等等。在此基础上，只需调整所有非叶子结点满足：sqList[i] 的关键码不小于 sqList[2i+1] 的关键码和 sqList[i] 的关键码不小于 sqList[2i+2]的关键码，则这样的完全二叉树就是一个最大堆。

如果把这 n 个记录看作是一棵完全二叉树的结点，则 sqList[0]对应完全二叉树的根， sqList[1]对应树根的左孩子结点， sqList[2]对应树根的右孩子结点， sqList[3]对应 sqList[1]的左孩子结点，sqList[4]对应 sqList[2]的右孩子结点，如此等等。在此基础上，只需调整所有非叶子结点满足：sqList[i] 的关键码不小于 sqList[2i+1] 的关键码和 sqList[i] 的关键码不小于 sqList[2i+2]
的关键码，则这样的完全二叉树就是一个最大堆。

下图1(a)所示是一棵完全二叉树，下图1(b)所示是一个最大堆。

类似地，最小堆的定义如下：
设顺序表sqList中存放了n个记录， 对于任意的i(0≤i≤n-1)， 如果2i+1 n时有 sqList[i] 的关键码不大于 sqList[2i+1] 的关键码；如果 2i+2 n 时有sqList[i] 的关键码不大于 sqList[2i+2] 的关键码，则这样的堆为最小堆。 如果把这 n 个记录看作是一棵完全二叉树的结点，则 sqList[0]对应完全二叉树的根， sqList[1]对应树根的左孩子结点， sqList[2]对应树根的右孩子点，sqList[3]对应 sqList[1]的左孩子结点，sqList[4]对应 sqList[2]的右孩子结点，如此等等。在此基础上，只需调整所有非叶子结点满足：sqList[i] 的关键码不大于 sqList[2i+1] 的关键码和 sqList[i] 的关键码不大于 sqList[2i+2] 的关键码，则这样的完全二叉树就是一个最小堆。下图(a)所示是一棵完全二叉树，下图(b)所示是一个最小堆。

由堆的定义可知，堆有如下两个性质：
（1）最大堆的根结点是堆中关键码最大的结点，最小堆的根结点是堆中关键码最小的结点，我们称堆的根结点记录为堆顶记录。
（2）对于最大堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递减有序的；对于最小堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递增有序的。
堆排序的过程是：设有 n 个记录，首先将这 n 个记录按关键码建成堆，将堆顶记录输出，得到 n 个记录中关键码最大（或最小）的记录。然后，再把剩下的n-1 个记录，输出堆顶记录，得到 n 个记录中关键码次大（或次小）的记录。如此反复，便可得到一个按关键码有序的序列。 

因此，实现堆排序需解决两个问题：
（1）如何将 n 个记录的序列按关键码建成堆；
（2）输出堆顶记录后，怎样调整剩下的 n-1 个记录，使其按关键码成为一个新堆。
首先，以最大堆为例讨论第一个问题：如何将 n 个记录的序列按关键码建成堆。
根据前面的定义，顺序表 sqList 中的 n 个记录构成一棵完全二叉树，所有的叶子结点都满足最大堆的定义。 对于第 1 个非叶子结点 sqList[i] （i=(n-1)/2） ,由于其左孩子结点 sqList[2i+1]和右孩子结点 sqList[2i+2]都已是最大堆，所以，只需首先找出 sqList[2i+1]结点和 sqList[2i+2]结点中关键码的较大者，然后与 sqList[i]结点的关键码进行比较，如果 sqList[i]结点的关键码大于或等于这个较大的结点的关键码，则以 sqList[i]结点为根结点的完全二叉树已满足最大堆的定义；否则，对换 sqList[i]结点和关键码较大的结点，对换后以sqList[i]结点为根结点的完全二叉树满足最大堆的定义。按照这样的方法，再调整第 2 个非叶子结点 sqList[i-1] （i=(n-1)/2） ，第 3 个非叶子结点sqList[i-2]，……，直到根结点。当根结点调整完后，则这棵完全二叉树就是一个最大堆了。
当要调整结点的左右孩子结点是叶子结点时，上述调整过程非常简单；当要调整结点的左右孩子结点不是叶子结点时，上述调整过程要稍微复杂一些。因为调整过后，可能引起以左孩子结点（或右孩子结点）为根结点的完全二叉树不是一个最大堆，这时，需要调整以左孩子结点（或右孩子结点）为根结点的完全二叉树，使之成为一个最大堆.

下图3

说明了如何把图1(a)所示的完全二叉树建成图1(b)所示的最大堆的过程。

第一步：从 i=(n-1)/2=(7-1)/2=3 开始，sqList[3]的关键码 27 小于sqList[7]的关键码 48， 所以， sqList[3]与 sqList[7]交换， 这样， 以 sqList[3]为根结点的完全二叉树是一个最大堆，如图(b)所示。

第二步：当 i=1 时，由于 sqList[1]的关键码 20 小于 sqList[3]的关键码48，所以将 sqList[1]与 sqList[3]交换，这样导致 sqList[3]的关键码 20 小于sqList[7]的关键码 27， 所以将 sqList[3]与 sqList[7]交换， 这样， 以 sqList[1]为根结点的完全二叉树是一个最大堆，如图(d)所示。

第三步：当 i=0 时，对堆顶结点记录进行调整，由于 sqList[0] 的关键码42小于sqList[1] 的关键码 48，所以将 sqList[0]与 sqList[1]交换，这样，
以 sqList[0]为根结点的完全二叉树是一个最大堆，如图(e)所示，整个堆建立的过程完成。

建堆的算法如下所示，算法中记录的比较表示记录关键码的比较，顺序表中只存放了记录的关键码。

//创建堆的算法

public void CreateHeap(SeqList int sqList, int low, int high) 

 //判断是不是 小于这个 最大值是否是小于 他的count

 if ((low high) (high = sqList.Last)) 

 // 他的j的值

 int j = 0; 

 //交换的变量

 int tmp = 0;

 //默认k的计数 

 int k = 0; 

 for (int i = high / 2; i = low; --i) 

 //取得的i值

 k = i; 

 //左子树

 j = 2 * k + 1; 

 //相应的变量

 tmp = sqList[i]; 

 while (j = high) 

 //寻找下一个值

 if ((j high) (j + 1 = high) 

 (sqList[j] sqList[j + 1])) 

 ++j; 

 //就想起商议5

 if (tmp sqList[j]) 

 sqList[k] = sqList[j]; 

 k = j; 

 j = 2 * k + 1; 

 else 

 j = high + 1; 

 sqList[k] = tmp; 

//双层循环 算法的时间的复杂度是O(n2)

把顺序表中的记录建好堆后，就可以进行堆排序了。

堆排序的算法如下所示，算法中记录的比较表示记录关键码的比较，顺序表中只存放了记录的关键码：

 1 //进行堆排序

 2 public void HeapSort(SeqList int sqList) 

 3 { 

 4 //当前的变量

 5 int tmp = 0; 

 7 //创建相应的队

 8 CreateHeap(sqList, 0, sqList.Last); 

10 //进行循环遍历

11 for (int i = sqList.Last; i --i) 

12 { 

13 //进行相应交换的值

14 tmp = sqList[0]; 

15 sqList[0] = sqList[i]; 

16 sqList[i] = tmp; 

17 //创建相应的值

18 CreateHeap(sqList, 0, i-1); 

19 } 

21 //由于用到递归，所以时间的复杂度是O(nlog2n)

下图4是图3(d)所示的最大堆进行堆排序的过程。
第一步：将堆顶记录（关键码为 48）与顺序表最后一个记录（关键码为 20进行交换，使得堆顶记录的关键码 20 比根结点的左孩子结点的关键码 42 小，于是重新调整堆（记录的范围是从顺序表的第一个记录到倒数第二个记录，为了表示出顺序表的最后一个记录不在调整的范围之内，下图4(a)已经把最后一个结点从完全二叉树中去掉，以下同）。调整过程见下图4(b)所示。
第二步：将堆顶记录（关键码为 42）与顺序表倒数第二个记录（关键码为17*）进行交换，使得堆顶记录的关键码 17*比根结点的左孩子结点的关键码 22小，于是重新调整堆（记录的范围是从顺序表的第一个记录到倒数第三个记录） 。调整过程见下图4(c)所示。
第三步： 将堆顶记录 （关键码为 27） 与顺序表倒数第三个记录 （关键码为 8）进行交换，使得堆顶记录的关键码 8 比根结点的左孩子结点的关键码 20 小，于是重新调整堆（记录的范围是从顺序表的第一个记录到倒数第四个记录） 。调整过程见下图4(d)所示。
第四步：将堆顶记录（关键码为 20）与顺序表倒数第四个记录（关键码为13）进行交换，使得堆顶记录的关键码 13 比根结点的左孩子结点的关键码 17*小，于是重新调整堆（记录的范围是从顺序表的第一个记录到倒数第五个记录） 。调整过程见下图4(e)所示。

第五步：将堆顶记录（关键码为 17*）与顺序表倒数第五个记录（关键码为8）进行交换，使得堆顶记录的关键码比根结点的右孩子结点的关键码 17 值小，于是重新调整堆（记录的范围是从顺序表的第一个记录到倒数第六个记录） 。调整过程见图 下图4(f)所示。
第六步： 将堆顶记录 （关键码为 17） 与顺序表倒数第六个记录 （关键码为 8）进行交换，使得堆顶记录的关键码 8 比根结点的左孩子结点的关键码 13 小，于1是重新调整堆（记录的范围是从顺序表的第一个记录到倒数第七个记录） 。调整过程见图4(g)所示。

第七步：将堆顶记录（关键码为 13）与顺序表第二个记录（关键码为 13）进行交换，调整过程结束。调整过程见图4(h)所示

堆排序是一种较难的排序，思路是构建堆，在排序。 下节我继续介绍排序的内容。

数据结构与算法 数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。在内存中储存管理数据的结构
数据结构与算法（一） 近日受北京疫情影响居家办公，给自己充充电，刷一遍 邓俊辉老先生的算法与数据结构教程，纯属学习笔记，有总结不当的地方欢迎指正~
数据结构与算法是什么？ 在计算机科学中，数据结构（Data Structure）是计算机中存储、组织数据的方式。为什么数据结构和算法经常放在一起讨论？算法用来设计一种使用计算机来解决问题的方法。设计高效的算法又是怎么来实现的？在我们学习了计算机编程后，也要学习数据结构与算法这些基础内容。
数据结构与算法——线性排序 前面已经说完了几种非线性排序，它们分别是时间复杂度为 O(n2) 、适合小规模数据的冒泡排序、选择排序、插入排序，和应用较广泛的时间复杂度为 O(nlogn) 的希尔排序、归并排序、快速排序。其实这几种排序都有一个特性，那就是它们都是基于数据的比较和移动，而今天介绍的这几种线性排序，他们的时间复杂度都是 O(n) ，因为不涉及到数据的比较和移动。