当前课程知识点：数据结构 > 第8章 排序 > 8.4 选择排序 > 讲解（中）
现在，我们来看第二种选择排序，堆排序
先来看堆的定义
我们将待排序列表示为完全二叉树T，之前我们讲过，完全二叉树
从上到下
从左到右，对结点进行编号
现在，我们将待排序的n个元素，放到完全二叉树当中
并且，让T中所有的非叶结点，均不大于其左右孩子
这时候的完全二叉树，就叫做小顶堆
比如，这棵完全二叉树
1，它的左右孩子3和2，是大于等于1的
或者说，1小于等于3和2，3小于等于4和3，2小于等于5
所有结点，都小于等于它的左右孩子
这时候，就是小顶堆，与之对应的，每一个结点都大于等于它的左右孩子，这时候，就是大顶堆
5大于等于3和4，3大于等于3和2
4大于等于1
这时候，就是大顶堆
很容易发现，堆的根一定是n个元素当中的最小者(或者最大者)
比如，这里的1，它作为树的根
它是这6个元素当中最小的
5是大顶堆的根，是6个元素当中最大的
现在，我们以小顶堆为例
如何找到次小者呢
整个堆的根是最小者
次小者如何找到呢
现在我们来看，我们用T的最后一个结点，来替换根结点
也就是，这里的7和1
我们交换一下位置
然后，从上到下，依次调整所有的非叶结点
从上到下，调整所有的非叶结点，最后一个非叶结点是4
以上过程称为一趟筛选
或者说一趟调整
现在，我们来调整这样一棵小顶堆
我们交换
当前树的根(也就是最小值1)和最后一个元素7
7作为新的根
从根结点开始
依次调整每一个非叶结点
要保证满足小顶堆的性质
现在，7和它的两个孩子3和2
我们应该将最小值，放到根的位置
所以，我们将2和7交换，交换了之后
3是满足小顶堆性质的
3小于等于4和6
没问题，下一个非叶结点7
这个7
它不满足小顶堆的性质
所以，我们应该将最小值4，和7进行交换
现在，我们就调整完毕了
那么，新的根就是次小值2
我们继续往下调整
最后，会将这n个元素调整完毕
需要注意
如果我们要排为正序
需要建立大顶堆
我们刚才是以小顶堆为例的
你会发现，小顶堆每次得到了一个最小值
它是和最后一个元素进行交换
它会把最小的，放到树的最下面
将来，我们对这棵树进行层次遍历的时候
得到的序列，恰恰是一个逆序的序列
所以，反过来说
你要得到正序的序列
需要建立大顶堆
现在，我们来看如何建立初始队
刚才，我们讲筛选(或者调整)的时候
我们是假定，已经有了一个小顶堆(或者大顶堆)的前提之下
然后进行调整
以找到次小值(或者次大值)
那你如何根据给定的n个元素的序列，建立一个初始的堆呢
现在我们来看
我们知道
如果把这n个元素，排成一个完全二叉树
我们之前讲过，完全二叉树的最后一个非叶结点
它的编号就是n/2向下取整
换句话说
第一个叶结点编号，是从n/2向下取整加1开始的
我们从下而上
这跟刚才筛选的方向不一样
从下而上
从最后一个非叶结点开始
依次调整所有的非叶结点
比如，我们现在对这样一棵8个结点的树
进行编号
8除2向下取整，4
所以，最后一个非叶结点，应该是7这个结点
我们从它开始，从下到上，一直调整到根结点
让每一个结点，都满足小顶堆的性质
现在，我们来开始调整
由于第一个非叶结点7
它(7)是大于它的孩子(4)的
所以交换
这个调整完毕了
再看这个，我们交换1和5
因为，我们始终是把
较小的(最小的)那个元素
作为当前树的根
变成1和5，交换1和5的位置
然后看它(3)
它满足小顶堆的性质
不用管，再调整根结点，我们要交换1和4，把4、3、1当中的最小者
1作为根，4拿下来
4拿下来之后
这棵子树就不满足小顶堆的性质了
于是，我们要将最小值2，跟4进行交换
从而所有的非叶结点调整完毕
我们就建立了一棵小顶堆
这棵树的根，就是这8个元素当中的最小值
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
