堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

在学习堆排序之前我们要先了解堆这种数据结构。

堆的定义如下：n个元素的序列{k1,k2，···，kn}当且满足以下关系时，称之为堆。

      若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：

树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。

对于一个小顶堆，若在输出堆顶的最小值之后， 使剩余n-1个元素的序列再次筛选形成一个堆，再输出次小值，由此反复进行，便能得到一个有序的序列，这个过程就称之为堆排序。

从上面对于堆排序的叙述我们知道，进行一次堆排序，我们要解决两个问题：

1、如何初始化一个堆

2、 如何在输出堆顶元素之后，调整堆内元素，使其再次形成一个堆。

下面我们先来研究第二个问题（为何这样看了下面的内容你就会明白），以小顶堆为例：

（1）在输出堆顶元素之后以堆中最后一个元素代替之

。

（2）此时根节点的左右子树都是堆，由于右子树根节点的值小于左子树根节点的值且小于根节点的值，则将9与2互换，互换之后我们发现右子树的堆结构被破坏了，这时我们将调整后的9作为根节点继续进行跟上面相同的调整，直到堆结构恢复。

通过上述的调整，我们得到了一个新堆。这也是一次筛选的过程。

其实，初始堆的过程也就是一个反复筛选的过程，若将此序列看成是一个完全二叉树，则最后一个非终端节点是（N/2）这也是我们筛选的开始点，从下至上进行筛选过程，最后得到有序序列也就是堆排序。（这一步比较难理解建议自己画图看着算法揣摩揣摩）。