图解堆排序（一）什么是堆和堆的性质

1. 引言

堆排序（Heap Sort）是一种非常高效的排序算法，堆（Heap）是一种数据结构，堆排序主要就是利用堆来进行排序；它是一种不稳定的排序算法。罗伯特·弗洛伊德和J·威廉姆斯于1964年共同发明了堆排序算法，其中的罗伯特·弗洛伊德是1978年的图灵奖得主。

为了不让本文篇幅过长，我们将该系列文章分为三篇：第一篇讲解什么是堆以及堆的性质，第二篇讲解堆的基本操作，第三篇讲解完整的堆排序；这是其中的第一篇。

2. 什么是堆

堆这种数据结构必须满足两个条件：

1. 堆首先必须是一棵完全二叉树；

2. 这棵完全二叉树中，任意一个结点的值都大于等于它的左右孩子结点的值，这样的堆称为大顶堆（也叫最大堆，Max-Heap）；或者任意一个结点的值都小于等于它的左右孩子结点的值，这样的堆称为小顶堆（也叫最小堆，Min-Heap）。

图1直观展示了堆，其中左边为大顶堆、右边为小顶堆。

图1 堆的结构：大顶堆和小顶堆

我们可以将一个堆存储在一个序列（数组）中，首先在堆中按照从上至下和从左至右的顺序为每个结点编号。结点编号从0开始，每个结点的编号就是它在序列中对应的下标。图2展示了如何将图1中的大顶堆存储到序列中，其中结点下面的数字表示该结点的编号。

图2 用序列存储堆

3. 堆的性质

为了加深对堆和堆排序算法的理解，这里总结了几条堆的性质。当按升序（从小到大）排序时，堆排序主要使用大顶堆；而使用降序（从大到小）排序时，堆排序主要使用小顶堆。我们以升序排序的方式讲解堆排序，降序排序的方式是类似的。所以下面这些性质其实是大顶堆的，但是小顶堆也有相同或相似的性质。这些性质都非常的简单，甚至是一目了然的。

1. 编号为 i 的结点（叶结点除外，因为它们没有孩子结点），它的左右孩子的编号分别为 2i+1 和 2i+2。比如结点1，它的左孩子的编号为2*1+1=3，而右孩子的编号为2*1+2=4。

2. 编号为 i 的结点（根结点除外，因为它没有父结点），它的父结点的编号为 ⌊(i - 1) / 2⌋；其中⌊⌋表示向下取整，⌊x⌋是小于等于x的最大整数。比如结点4，它的父结点的编号为⌊(4-1)/2⌋ = ⌊1.5⌋ = 1。

3. 有n个结点的堆，它的深度为⌊log2(n)⌋+1；比如图2中的大顶堆有9个结点，它的深度为4，满足4=⌊log2(9)⌋+1。

4. 一个堆的第i层最多有2^(i-1)个结点；比如图2中的大顶堆的第3层共有4个结点，满足4=2^(3-1)。

5. 大顶堆的根结点必定是它所有结点中最大的那一个。

6. 大顶堆的左右子树都是大顶堆，其实以大顶堆的任意一个结点为根的子树都是大顶堆。

7. 删掉大顶堆的最后一个结点（它必定是叶结点），剩余的所有结点依旧组成一个大顶堆；因为删掉最后一个结点后，其余结点依旧组成一棵完全二叉树，并且依旧满足任意一个结点的值都大于等于它的左右孩子结点的值。

4. 堆排序的主要思想

本文最后我们再概述一下堆排序的主要思想，这主要是为了引出堆的操作，具体的细节留待后文再介绍。假设待排序的原序列共有n个元素，并且按照升序（从小到大）排序，那么堆排序的步骤如下：

1. 首先将该原序列构造为一个大顶堆，这个大顶堆依旧存储在该序列中。

2. 选择该大顶堆的根结点（下标为0）并和序列中的最后一个元素交换位置；现在原序列中最大的元素位于序列中最后的位置上，而该大顶堆除它的根结点外的所有剩余结点都在序列的前n-1个位置上。

3. 然后对序列的前n-1个元素进行调整，使它们重新形成一个大顶堆，再选择该大顶堆的根结点（下标还是为0）并和序列中的倒数第二个元素交换位置；现在原序列中第二大的元素位于序列的倒数第二个位置上，该大顶堆的剩余结点都在序列的前n-2个位置上。

4. 再对序列的前n-2个元素进行调整，同样使它们重新形成一个大顶堆，选择该大顶堆的根结点（下标还是为0）并和序列中的倒数第三个元素交换位置；现在原序列中第三大的元素位于序列的倒数第三个位置上，该大顶堆的剩余结点都在序列的前n-3个位置上。

5. 重复这一过程，直到整个序列中的元素都排好序。

根据上面讲到的堆排序的主要思想，我们可知堆排序面临两个主要的问题：

1. 将一个序列构造为一个大顶堆；

2. 将一个大顶堆的根结点取出后，调整它的剩余结点以使它们形成一个新的大顶堆。

如何解决这两个问题涉及堆的操作，我们将在下一篇文章中再详细讲解。

（完）