本文从说到，再使用的有序性对无序数列排序。

1. 树

是最基本的数据结构，可以用映射现实世界中一对多的群体关系。如公司的组织结构、网页中标签之间的关系、操作系统中文件与目录结构……都是用树结构描述的。

树是由以及所构成的集合。树结构更多概念不是本文的内容，本文只关心树数据结构中的几个特殊变种：

如果树中的任意结点（除叶结点）最多只有两个子结点，这样的树称为。

如果 中任意结点的子结点（除叶结点）都有 个，则称为。

满二叉树的特性：

根据的定义可知，从上向下，每一层上的结点数以 倍的增量递增。也可以说，满二叉树是一个首项为 ，公比为 的等比数列。所以：

一个层数为 的满二叉树总结点数为：2-1 。

满二叉树的总结点数一定是奇数！

根据等比公式可知第 层上的结点数为：2，因此，一个层数为 的满二叉树的叶子结点个数为（也就是最后一层）: 2。

什么是完全二叉树？

是的一个特例。

通俗理解：在基础上，从右向左删除几个叶子节点后，此时满二叉树就变成了完全二叉树。如下图，在上图满二叉树基础上从右向左删除 个叶结点后的结构就是完全二叉树。

完全二叉树的专业概念：

一棵深度为 的有 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 的结点与满二叉树中编号为 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

专业概念有点像绕口令。

显然，完全二叉树的叶子结点只能出现在最下层或次下层，且最下层的叶子结点集中在树的左部。

注意：满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

2. 二叉堆

是有序的 ，在的基础上， 提供了有序性特征：

的根结点上的值是整个堆中的或。

当根结点上的值是整个堆结构中的最小值时，此堆称为最小堆。

如果根结点上的值是整个堆结构中的最大值时，则称堆为最大堆。

最小堆中，任意节点的值大于父结点的值，反之，最大堆中，任意节点的值小于父结点的值。

综合所述，二叉堆的父结点与子结点之间满足下面的关系：

如果知道了一个结点的位置 ，则其左子结点在 处，右子结点在 处。

如果有子结点。

如果知道了一个结点的位置 ，则其父结点在 除 处。

根结点没有父结点。

如上图所示：

值为 的结点在 处，则其左结点 的位置应该在 处，而实际情况也是在 4 位置。其右子结点 的位置应该在 的位置，实际位置也是在 位置。

值为 的结点现在 位置，其父结点的根据公式 除 等于 (取整)，应该在 处，而实际情况也是在 处（位置在 、 值为 的结点是其父结点）。

2.1 二叉堆的抽象数据结构

当谈论某种数据结构的抽象数据结构时，最基本的 无非就是增、删、改、查。

二叉堆的基本抽象数据结构：

：创建一个新堆。

：向堆中添加新节点（数据）。

：返回最小（大）堆的最小（大）元素。

：删除根节点。

：判断堆是否为空。

：查询堆中所有数据。

虽然是树结构的变种，有树的层次结构，但因结点与结点之间有很密切的数学关系，使用 中的列表存储是非常不错的选择。

现如有一个数列=，现使用二叉堆方式保存。先构造一个列表。

列表中的第 位置初始为 ，从第 个位置也就是索引号为 的地方开始存储堆的数据。如下图，二叉堆中的数据在列表中的存储位置。

2.2 API 实现

设计一个 类封装对二叉堆的操作方法，类中方法用来实现最小堆。

类中的属性详解：

：使用列表存储的数据，初始时，列表的第 位置初始为默认值 。

为什么要设置列表的第 位置的默认值为 ？

这个 也不是随意指定的，有其特殊数据含义：用来描述根结点的父结点或者说根结点没有父结点。

：用来存储二叉堆中数据的实际个数。

类中的方法介绍：

：检查是不是空堆。

：创建根结点。保证根节点始终存储在列表索引为 的位置。

：如果是最大堆，则返回二叉堆的最大值，如果是最小堆，则返回二叉堆的最小值。

使用列表保存二叉堆数据时，根结点始终保存在索引号为 的位置。

前面是几个基本方法，现在实现添加新结点，编码之前，先要知道如何在二叉堆中添加新结点：

添加新结点采用上沉算法。如下演示流程描述了上沉的实现过程。

把添加到已有的的最后面。如下图，添加值为 的新结点，存储至索引号为 的位置。

查找的，并与的值比较大小，如果比父结点的值小，则和交换位置。如下图，值为 的结点小于值为 的父结点，两者交换位置。

交换后再查询是否存在父结点，如果有，同样比较大小、交换，直到到达根结点或比父结点大为止。值为 的结点小于值为 的父结点，继续交换。交换后，新结点已经达到了根结点位置，整个添加过程可结束。观察后会发现，遵循此流程添加后，没有破坏二叉堆的有序性。

方法的实现：

测试向二叉堆中添加数据。

创建一个空堆。

创建值为 的根结点。

检查根结点是否创建成功。

添加值为 和值为 的 个新结点，检查添加新结点后整个二叉堆的有序性是否正确。

添加值为 的新结点，并检查二叉堆的有序性。

继续添加值为 、、 的 个新结点，并检查二叉堆的状况。

介绍完添加方法后，再来了解一下，如何删除二叉堆中的结点。

的删除操作从根结点开始，如下图删除根结点后，空出来的根结点位置，需要在整个二叉堆中重新找一个结点充当新的根结点。

二叉堆中使用下沉算法选择新的根结点：

找到二叉堆中的最后一个结点，移到到根结点位置。如下图，把二叉堆中最后那个值为 的结点移到根结点位置。

最小堆中，如果的值比左或右子结点的值大，则和子结点交换位置。如下图，在二叉堆中把 和 的位置进行交换。

注意：总是和最小的子结点交换。

交换后，如果还是不满足最小二叉堆父结点小于子结点的规则，则继续比较、交换直到下沉到二叉堆有序为止。如下，继续交换 和 的值。如此反复经过多次交换直到整个堆结构符合二叉堆的特性。

方法的具体实现：

方法依赖 和 方法：

方法用查找比父结点小的结点。

方法用来查找是否存在子结点。

测试在二叉堆中删除结点：

可以看到最后二叉堆的结构和有序性都得到了完整的保持。

3. 堆排序

堆排序指借助堆的有序性对数据进行排序。

需要排序的数据以堆的方式保存

然后再从堆中以根结点方式取出来，无序数据就会变成有序数据 。

如有数列=[4,1,8,12,5,10,7,21,3]，现通过堆的数据结构进行排序。

本例中的代码还有优化空间，本文试图讲清楚堆的使用，优化的地方交给有兴趣者。

4. 后记

在树结构上加上一些新特性要求，树会产生很多新的变种，如二叉树，限制子结点的个数，如满二叉树，限制叶结点的个数，如完全二叉树就是在满二叉树的“满”字上做点文章，让这个""满"变成"不那么满"。

在完全二叉树上添加有序性，则会衍生出二叉堆数据结构。利用二叉堆的有序性，能轻松完成对数据的排序。

二叉堆中有 2 个核心方法，插入和删除，这两个方法也可以使用递归方式编写。

关键词： Python 一网打尽排序算法之堆排序算法中的树