浅谈堆排序
堆排序可以做什么
首先应该弄清楚堆排序可以解决什么问题，答案是显而易见的：排序。说得通俗点儿就是对一组无序的数字进行调整，使其按照从大到小或者从小大到的顺序有序排列。我们习惯性的采用数组这一数据结构来记录一系列有序或者无序的数据。
故我们可以借助堆排序这种方法，将以下无序数组:
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
调整为有序数组：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
以下讲解的所有内容都是为了将上述无序数组经过堆排序后调整为从大到小的有序数组。
什么是堆
上一小节重在堆排序中的“排序”二字，这一节我们来唠唠“堆”。我在没有接触“堆”这个概念之前，确实感觉丈二和尚摸不着头脑，甚至还会与“堆内存”的“堆”概念联系起来。下面就让我们先来看看堆的定义吧。
根据《Data Structures and Algorithm Analysis in C》(中文译名：《数据结构与算法分析》）和百度百科的相关资料，堆必须同时具备两个特性：1、结构性；2）堆序性。
- 结构性
堆是一棵完全二叉树，所谓完全二叉树即叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
以如下无序数组A为例
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
可将其表示为完全二叉树的形式(从左至右，从上到下依次填入二叉树)：
数组的二叉树表示
提到二叉树就不得不提父节点与左、右子节点的概念。在二叉树中，一个父节点的子节点数的取值范围为[0,2],子节点数为零的父节点常被称为叶子节点。每一个父节点又可以看成是其子树分支的根节点。
综合数组和二叉树解结构来看，在知道了某一数字在数组中的索引后，可以很方便地计算出二叉树中该数字的左右子节点，或者父节点在数组中的索引。
以数字5为例，它的数组表示为A[1],根据二叉树，其父节点为4，即A[0];同时其左节点为2，右节点为6，分别对应A[3],A[4]。
故可得出一个结论，A[i]的左节点为A[2i+1],右节点为A[2i+2]，父节点为A[i/2]，它从数组索引的角度描述了数字与数字在二叉树中的位置关系。（1、在应用此结论时需确认A[i]存在相应的左节点、右节点、根节点；2、此结论在后面会反复用到；3、此结论实际上是完全二叉树的一个基本性质，这也是为什么堆的结构性要求其满足完全二叉树的形式，就是为了使用此结论）
- 堆序性
堆序性说得通俗一点儿就是，父节点中的元素不小于（不大于）任意子节点的元素。这里的元素在本文中是以数字体现的。注：本文只讨论“大根堆”，即父节点中的元素不小于任意子节点的元素这种情形。所以，在一个大根堆中，一个节点的元素在其子树所有元素组成的集合中必定是最大值。这一结论至关重要。
以下给出了两个大根堆的示例：
大根堆示例
元素下沉
在正式讲解堆排序的实现步骤之前，先说一下十分有用的“元素下沉”方法，此方法可谓是堆排序的精华之所在。何为“元素下沉”？估计很少有人知道这个词语的意思，不知道也没关系，因为这是我造的一个词语...... :)，书本上有专门的词汇，我觉得太过生硬，就自作主张起了一个别称，本文会一直沿用这个词语。
给定一个完全二叉树，除了根节点以外，此二叉树满足“堆序性”，“元素下沉”的目的是在此二叉树中将根节点的元素放至合适的坑位，相应地调整其他元素，最终使得包括根节点在内的整棵二叉树都满足“堆序性”。
“元素下沉”的实施方案说来也很简单：当父节点的元素值小于左子节点的元素值或者右子节点的元素值时，将父节点的元素值与左右子节点较大的元素值进行交换，针对交换后的父节点，循环执行“元素下沉”操作，“元素下沉”的终止条件就是父节点的元素值不小于其任意左右子节点的元素值，或者当前父节点无子节点（即当前节点为叶子节点）。
以上给出了实施方案，下面就直接贴出实现代码（以整数序列为例）：
//给定父节点的索引，得到左子节点的索引
#define LeftChild(i) (2*(i)+1)
//元素下沉方法
void PercDown(int A[], int i, int N)
{
//子节点的索引号
int child;
//存储当前父节点元素的临时变量
//(注：每一个节点都可以看作是其子树的根节点)
int tmp;
for (tmp = A[i]; LeftChild(i)<N; i = child)
{
child = LeftChild(i);
//挑选出左、右子节点中较大者
if (child != N-1 && A[child+1]>A[child])
{
child++;
}
//比较当前父节点与较大子节点
if (A[i]<A[child])
{
//交换当前父节点处的元素值与较大子节点的元素值
tmp= A[i];
A[i] = A[child];
A[child] = tmp;
}
else
{
break;
}
}
}
下面给出一个简单的示例来说明“元素下沉”的过程：
元素下沉
原始二叉树中，除去根节点（元素1），其子树满足堆序性，为了使得整棵完全二叉树都满足堆序性，需要为元素1找到合适的放置位置，并相应地调整其它元素的位置。
实现此功能的对应代码为：
int A[] = {1,5,6,3,2,4};
PercDown(A, 0, 6);
第一次循环中，根节点的元素1与左右子节点中较大的6进行比较，由于1<6,故1与6交换位置，第二次循环中，1与左右节点中较大的4进行比较，由于1<4,故1与4交换位置,又由于此时元素1作为当前父节点时不存在左右子节点，故“元素下沉”操作到此结束，最终得到一个具有堆序性的完全二叉树。
堆排序的具体实现
下面开始进入正题了，堆排序算法究竟是怎么实现的呢？其实只需要简单的两步就可以实现堆排序：1）根据无序数组创建一个大根堆；2）不断调整大根堆，使其到达有序。
- 创建大根堆
给定了一个无序数组，用二叉树的形式表现该数组时并不一定是大根堆。比如
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
对应的二叉树为
原始二叉树
不难发现此二叉树不满足“堆序性”。那么如何根据一个无序数组构建一个大根堆呢？秘诀就在于上一节提到的“元素下沉”方法。
在此之前我们先来分析一下由无序数组构建的二叉树。仔细观察可发现：仅仅考虑二叉树中所有的叶子节点，它们必定是满足“堆序性”的。
叶子节点
元素2、6、1已经满足了“堆序性”，故我们的目标是调整剩余的父节点，使得整棵二叉树都满足“堆序性”，最终构建出一个大根堆。
俗话说饭要一口一口的吃，构建大根堆的过程亦然，在已经满足“堆序性”的元素集合中新增一个元素，采用“元素下沉”法进行调整，形成新的满足“堆序性”的元素集合，在此基础上再添加一个新的元素，并采用“元素下沉”法，如此循环，直到所给无序数组的所有元素都满足“堆序性”，则完成了大根堆的构建。
下面结合实例进行分析，目前已知元素2、6、1满足了堆序性，在此基础上添加元素3，二叉树的形式表示为：
添加元素
发现添加元素3后仍然满足堆序性，无需采用“元素下沉”法进行调整。在此基础上添加元素5，表示为二叉树的形式为：
添加元素
发现引入元素5之后，破坏了“堆序性”。此时上一节讨论的“元素下沉”法就能派上用场了。还记得“元素下沉”法的应用条件吗? 除了根节点以外，此二叉树满足“堆序性”,在这里就是指除了元素5以外，其他元素满足 “堆序性”。 这里调用一次“元素下沉”方法后得到的输出结果为：
元素下沉
好的，到目前位置就差最后一个元素了。现在我们把元素4加入其中，得到的二叉树为：
添加元素
很遗憾，添加元素4后导致整个二叉树并不满足“堆序性”，故又需要调用“元素下沉”方法对二叉树进行调整。调整的过程大致为：
构建大根堆
至此，根据一个无序数组构建大根堆的工作就完成了!
在这里需要说明一点，给定一个无序数组，可以构建出多个大根堆，即其对应的大根堆并不是唯一的。上述构建方法只是构建了其中的一个大根堆，我们的目的是构建一个大根堆，具体是哪一个并无影响。
以下给出了相同无序数组对应的其他大根堆示例：
不同的大根堆
- 调整大根堆
得到了大根堆，我们的工作就完成了一半。首先要思考一下为什么花了这么大力气去构建一个大根堆呢？答案已经呼之欲出了，没错，大根堆的根元素必然是整个堆中的最大值。
回到先前我们构建的大根堆
大根堆
不难发现根元素6正是最大值。好的，下面有个小技巧，大家擦亮眼睛看好喽~
首尾互换
没错，就是将根节点元素与最后一个叶子节点的元素交换位置，这样做产生了两个后果：1）最大值6被挑选出来，并置于末位；2）根节点元素1打乱了“堆序性”。
对于第1）点，正式我们所期望的，但是第2）点不是我们希望出现的结果，那该怎么呢？此时又该“元素下沉”法出场了！目的是为了调整根节点元素1至合适的“坑位”，使得二叉树满足“堆序性”。 在这里需要说明的一点是，由于元素6已经确定为最大值，故此次可以不用参与“元素下沉”的过程，即“元素下沉”只在以下二叉树中开展：
元素下沉
也就是说元素6现在已经被确定为最大值，没有再与其他元素进行比较的意义了。
以下为针对根节点元素1进行“元素下沉”后的结果：
下沉后的结果
此时，不考虑末位的元素6，二叉树又满足了“堆序性”！（至此元素6将不参与任何“元素下沉”操作，元素6的位置已经是最终的位置，因此后续讨论的二叉树可以将元素6排除在外！）
按照刚才的流程，我们把根节点元素，也就是当前的最大值5与末位元素1进行交换，再进行“元素下沉”操作：
调整堆
由此，我们已经得到了无序数组中最大的两个值5、6，且他们均位于二叉树的末尾处。后面的操作也都是在“首尾交换”、“元素下沉”两个操作中来回切换，直至所有元素全部变为有序元素，如下图所示：
调整堆
将最终调整完成的二叉树写成数组形式，可得到：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
可以看出，调整大根堆的过程就是自下而上循环进行“首尾交换”和“元素下沉”操作的过程，目的只有一个：将较大元素调整至末位处！
至此，堆排序的工作全部完成，我们由一个无序数组，经过堆排序操作后得到了一个有序数组。
完整代码
以上都侧重于过程分析，下面给出堆排序的完整代码(元素下沉方法前面已经给出，这里不再重复)：
//堆排序
void HeapSort(int A[], int N)
{
int i;
//步骤一：创建大根堆
for (i = N/2; i>=0; i--)
{
PercDown(A, i, N);
}
//步骤二：调整大根堆
for ( i = N-1; i > 0; i--)
{
//首尾交换
Swap(&A[0], &A[i]);
//元素下沉
PercDown(A, 0, i);
}
}
//交换两个元素的位置
void Swap(int *num1, int * num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//主函数
void main()
{
int A[6] = {4,5,3,2,6,1};
HeapSort(A, 6);
}
运行此代码，数组A将由
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
调整为
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
至此，讲完！收工！！
温馨提示
本文一直在讨论大根堆，最后将数组调整为从小到大的顺序。其实小根堆的实现原理和操作方法与大根堆完全一样，只是大小顺序的问题，大家有兴趣也可以尝试用小根堆实现排序，将无序数组调整为从大到小的顺序！
后记
- 撰写本文的时间比较分散，所以条理会有点混乱。
- 文中若有错误的地方，还希望大家能够指出，或者有疑问的地方，也可以相互交流。
- 这是我的简书处女作，希望以后能写出更多的作品：）
