前言

堆排序是一种选择排序。

选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

算法思想

堆排序是利用堆的性质进行的一种选择排序。

动态效果示意图：

堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：

Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整；

如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个结点，元素3和元素8。

元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。

元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：

设当前元素在数组中以R[i]表示，那么，

(1) 它的左孩子结点是：R[2*i+1];

(2) 它的右孩子结点是：R[2*i+2];

(3) 它的父结点是：R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；

然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；

如此反复，直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作：

（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。

（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下，如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后，我们来看一下完整的堆排序处理：

还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。 

看完上面所述的流程你至少有一个疑问：

如何确定最后一个非叶子结点？

其实这是有一个公式的，设二叉树结点总数为 n，则最后一个非叶子结点是第 ⌊n/2⌋ 个。

代码实现

#include <iostream>
using namespace std;
//调整堆
void HeapAdjust(int *a, int i, int n) {
    int lc = i << 1;
    int rc = (i << 1) + 1;
    ...

课后习题

【2018年真题】在将数据序列（6, 1, 5, 9, 8, 4, 7) 建成大根堆时，正确的序列变化过程是（）

A. 6,1,7,9,8,4,5    →    6,9,7,1,8,4,5    →    9,6,7,1,8,4,5    →    9,8,7,1,6,4,5    
B. 6,9,5,1,8,4,7    →    6,9,7,1,8,4,5    →    9,6,7,1,8,4,5    →    9,8,7,1,6,4,5    
C. 6,9,5,1,8,4,7    →    9,6,5,1,8,4,7    →    9,6,7,1,8,4,5    →    9,8,7,1,6,4,5    
D . 6,1,7,9,8,4,5    →    7,1,6,9,8,4,5    →    7,9,6,1,8,4,5    →    9,7,6,1,8,4,5    → 9,8,6,1,7,4,5

参考答案：A

【2015年真题】已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。

A．1    B．2        C．3    D．4

参考答案：C 

【2011年真题】已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）
A．1
B．2
C．4
D．5 

解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。 

【2009年真题】已知关键字序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是（）。 

A．3，5，12，8，28，20，15，22，19 
B．3，5，12，19，20，15，22，8，28 
C．3，8，12，5，20，15，22，28，19 
D．3，12，5，8，28，20，15，22，19

参考答案：A
答案解析：考查小根堆的调整操作。 
小顶堆在逻辑上可以用完全二叉树来表示，根据关键序列得到的小顶堆的二叉树形式为下图左图： 

插入关键字 3 时，先将其放在小顶堆的末端，再将该关键字向上进行调整，得到的结果上图右边所示。所以，调整后的小顶堆序列为：3，5，12，8，28，20，15，22，19。