C++ 不知树系列之二叉排序堆

1.  前言

什么是二叉堆？

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

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

当上的值是整个堆结构中的最小值时，此堆称为。最小堆中，任意节点的值大于父结点的值。

当上的值是整个堆结构中的最大值时，则称堆为。最大堆中，任意节点的值小于父结点的值。

根据完全二叉树的特性，二叉堆的父结点与子结点之间满足下面的关系：

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

Tips： 前提是存在有子结点。

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

Tips： 根结点没有父结点。

如上图所示：

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

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

2 堆的数据结构

2.1  二叉堆的抽象数据结构

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

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

：创建一个新堆。

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

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

：删除根节点。

：判断堆是否为空。

：查询堆中所有数据。

根据的特性，顺序存储应该成为堆的首选方案。

如有数列=，可以先创建一个一维数组。

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

2.2   基础 API  实现

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

类中的属性详解：

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

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

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

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

类中的方法介绍：

：检查是不是空堆。逻辑较简单。

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

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

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

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

2.3 上沉算法

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

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

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

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

编码实现 方法

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

输出结果：

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

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

2.4 下沉算法

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

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

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

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

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

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

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

方法的具体实现：

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

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

3. 堆排序

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

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

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

如有数列=，现通过堆的数据结构进行排序。

输出结果：

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

4. 后记

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

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

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