知识点：堆排序

堆排序好像还是第一次考(2021上)。还连续考了两个题。

---

    根据软设第五版170页对于堆的定义，我们可以总结到(到底什么是题干中提到的大顶堆)：

只要在每一棵子树中，根的值都大于(或都小于)左右孩子的值(注意其中左右孩子之间的值不进行大小对比，也就是不管兄弟节点之间如何排序，只管父子之间如何排序)，那么这整个二叉树(从根开始，从左往右，从上到下数出来的序列，也就是题干中所说的用数组表示出来的一个序列)就叫堆。当条件中所有根的值都大于其左右孩子的值时，就就叫大根堆(或者题干中所说的大顶堆)。

    根据书上的图解(图3-56)或者两个函数实现，我们可以总结到(如何确定出题干中要求的大顶堆)：

子树个体中的对比原则是先左孩子再右孩子依次和子树的根进行比较，只要比较成功就进行根和子孩子的交换。每一棵子树整体对比顺序原则是从右往左、从下往上原则，直到对比完整棵树的根，那么就确定出来了一个初始堆。题目中要求的就是这个初始大根堆。另外要进行堆排序，弄出一个排好序的序列(大根堆只是找到最大的根了，也就是整个序列的最大的值了，其实还没有排好序)，可以查看参考书或者参考前面一个题 www.z21.org/question/97

---

解题：

然后草稿的解题过程是：

1、：按照数组A的数量，画一个完全二叉树的结构。

2、：把数组A里面的值，在完全二叉树中按照从做左到右、从上到下的顺序(其实就是广度优先)一一放进去。

3、：把完全二叉树从右往左、从下到上的顺序划分最小二叉子树，依次在子树中用子树的根和左孩子进行比较，比较成功就交换位置，失败就保留；再用子树的根和右孩子进行比较，比较成功就交换位置，失败就保留。

在第3步所有子树比较完成之后，在整个二叉树中，按照从左到右从上到下的顺序(其实就是从根开始广度优先)进行遍历，就是把二叉树值又还原的排成一行。这一行序列(就是题干中说的按数组表示)，就是C选项。