堆排序算法的基本思想

堆排序定义

一般来说，算法就像数学公式，前人经过不断优化和验证得到有规律性的公式留给后人使用，当然也会交给后人验证的思路。那么堆排序算法就是这样，它有基本固定的定义如下：

1、将数组构建为一颗有规则的完全二叉树

2、该二叉树任意父结点值必须大于（最大堆）或小于（最小堆）孩子结点

3、该二叉树除了最底层外，其它层都是从左往右充满地

4、该二叉树任意父结点左孩子数组下标 = 父结点数组下标 * 2

5、该二叉树任意父结点右孩子数组下标 = 父结点数组下标 * 2 + 1

6、该二叉树任意孩子父结点数组下标 = 孩子结点数组下标 / 2

7、该二叉树高度（所有父结点）= 数组长度 / 2

8、最后再对构建好的二叉树进行排序

图解堆排序

下面我们通过堆排序算法来实现。

构建最大堆二叉树

将数组构建为一颗有规则的完全二叉树，该二叉树遵循任意父结点必须大于（最大堆）孩子结点。当然，构建最小堆也是可以的，具体看场景来设计，一般从小到大排序可以选择最大堆，从大到小排序可以选择最小堆。当然最大堆也可以实现从大到小排序。

最大堆二叉树定义如下：

1、左孩子结点数组索引=父结点数组索引 * 2。伪代码如下：

private int leftIndex(int i) { return 2 * i;}

2、右孩子结点数组索引=父结点数组索引 * 2 + 1。伪代码如下：

private int rightIndex(int i) { return 2 * i + 1;}

3、父结点数组索引=孩子结点数组索引 / 2

private int parentIndex(int i) { return i / 2;}

为了描述直观，数组下标从1开始，但实际编写代码在操作数组取值时候需要减去1，因为实际程序中的索引是从0开始的。

假设我们按数组顺序开始构建

上图满足了父子结点直接的数组索引计算定义，但是它不满足最大堆的定义（任意父结点必须大于孩子结点），父结点6比右子结点9要小，所以我们需要对原数组值进行交换（注意：只是将两个下标对应的值进行交换，下标不变）来满足最大堆二叉树的定义，调整后结果如下:

此时，再根据定义绘制最大堆二叉树如下:

下面我们继续按这种思路构建左孩子结点数组值为3下标为2的左右孩子结点，构建结果如下：

按照下标计算公式构建如下：

按照最大堆定义中任意父结点必须大于孩子结点交换后如下：

此时，我们发现，当我们将父结点值为3和右孩子结点值为13交换后，13、8、3这颗小二叉树是满足定义了，但是上一个9、3、6小二叉树变成了9、13、6，明细不满足父结点值（9）大于子结点（13）的要求，需要继续将9和13的值交换才是正确的。但是我们思考一下，如果那个9原始值是7呢，把7跟13交换后，第二个小二叉树7、8、3又不满足要求了。由此我们思考按顺序构建可能是有问题的，不但要往上检查，还要往下检查，反复如此，知道满足定义为止，我们思考，这肯定不是最优的方式，那么有没有更好的方式呢？

答案是有，那就是反过来自底向上构建，先构建最末尾的那个父结点，再一层层向上构建，这样好处是每次构建上层的时候前面构建好的那个下层父结点会作为上层的子结点，如果这个子结点（下层的父结点）跟上层父结点发送交换，那么证明这个子结点必定大于下面所有子结点，只需要往下检查即可，不需要往上检查，这样减少程序执行的步骤进一步优化了算法。

现在问题来了，我们怎么获取到最末尾的父结点，实现自底向上进行构建呢？

根据上面的定义：”该二叉树高度（所有父结点）= 数组长度 / 2” 我们可以很容易写出自底向上构建的代码如下：

/** * 自底向上构建最大堆 * * @param param 待排序数组参数 */private void buildMaxHeap(Integer param) { //自底向上构建最大堆, 数组长度的前面一半都是父结点 int parentIndex = param.length / 2; for (int i = parentIndex; i > 0; i–) { //构建最大堆 this.maxHeap(param, i, param.length); }}

构建最大堆maxHeap代码如下：

/** * 构建最大堆必须满足以下要求： * 1、除了根以外的所有结点i都要满足 param[parentIndex(i)] >= param * 2、反过来就是任意父结点值必须大于孩子结点，最顶根父结点值是整颗树的最大值 * * @param param 待排序数组参数 * @param parentIndex 给定任意父结点索引 * @param heapLength 堆长度(一般就是数组长度) */private void maxHeap(Integer param, int parentIndex, int heapLength) { //计算左孩子结点数组下标 int leftIndex = leftIndex(parentIndex); //计算右孩子结点数组下标 int rightIndex = rightIndex(parentIndex); //最大值数组下标,默认是父结点 int maxValIndex = parentIndex; //如果左孩子结点值比父结点的值要大，则不满足最大堆要求 //因为下标我们从1开始，所以每次取值减去1保证数组不越界 if (leftIndex <= heapLength && param[leftIndex – 1] > param[parentIndex – 1]) { //这里记录最大值数组下标为左孩子结点 maxValIndex = leftIndex; } //如果右孩子结点值比前面计算得到的最大值要大，则不满足最大堆要求 if (rightIndex <= heapLength && param[rightIndex – 1] > param[maxValIndex – 1]) { //这里记录最大值数组下标为右孩子结点 maxValIndex = rightIndex; } //如果确定父结点的确不是最大值 if (maxValIndex != parentIndex) { //需要把最大值数组下标位置的值(左或右孩子)交换到父结点下标的位置 Integer oldParentVal = param[parentIndex – 1]; param[parentIndex – 1] = param[maxValIndex – 1]; //交换后，下标为maxValIndex的结点的值是原来父结点的值 param[maxValIndex – 1] = oldParentVal; //经过交换后，以maxValIndex下标作为父结点的子树又可能违反最大堆的性质 //因此这里需要继续递归调用maxHeap maxHeap(param, maxValIndex, heapLength); }}

下面我们重新根据原始数组按照自底向上的方式构建最大堆二叉树，根据计算计算公式（8 / 2）计算得到最末尾的父结点为4:

1、构建最末尾父结点（8/2=4）

2、构建倒数第二个父结点（8/2-1=3）

实际上我们需要足够细心，值进行交换后数组已经发生变化，之前父节点下标为3构建前值为9，现在构建引起的交换后值为左孩子结点6的值16，左孩子结点下标6的值变为原来父节点下标为3的值。

除此之外，我们还需要再细心点，就是每次发生交换值后，需要向下检查，这点后面我们还会再次提到和演示。

3、构建倒数第二个父结点（8/2-2=2）

4、构建倒数第一个父结点（8/2-3=1）

5、最后一个父结点交换值后如下图，我们上面说过，每次交换值后需要向下检查，发现下标为3的父结点6小于它的左孩子结点9，需要再次交换。

6、构建好最终最大堆如下

堆排序

我们发现构建好的最大堆有一个特点，就是根一定是整棵树最大值，如果构建的是最小堆，那么就反过来，根是整棵树最小值。但是，我们还发现除此之外该根的左右孩子结点是以它们为父节点的下面所有孩子结点的最大值，下面我们就是通过该特点将堆进行排序。

1、我们先看下经过最大堆二叉树构建前后数组是这样的:

2、因为我们是从小到大排序，而构建最大堆后第一个下标一定是最大值，所以我们将第一个下标交换到数组的最后位置。

3、交换后，整个数组又违反了最大堆二叉树，咋办呢？很简单，我们根据上面的思路，每次交换值后需要基于交换后的孩子节点（孩子结点也是其它孩子结点的父节点）向下检查，我们可以调用函数:

maxHeap(Integer param, int parentIndex, int heapLength) param：当前数组传入parentIndex：下标1，因为下标1跟最后下标8交换后该父节点肯定违背了定义heapLength: 这里传入8-1=7。因为1已经排好序，剩下还有7个元素需要排序

1、 将根结点交换后，堆长度剩下7个元素，最大堆的根结点放到数组最后

2、 。下面通过图解方式帮助理解：

注意，算法讲究尽可能最优，剩下最后两个元素不必再走maxHeap构建最大堆逻辑，直接交换即可，堆排序代码如下：

private Integer heapSortAsc(Integer param) { if (param == null || param.length < 1) { return param; } //先自底向上构建最大堆 this.buildMaxHeap(param); //累计处理的数量 int handlerNum = 0; //数组最大下标 int heapLength = param.length; //最后两个下标0,1不用走构建最大堆,直接交换位置即可 int endIndex = 2; for (int i = heapLength; i > endIndex; i–) { //拿出堆最顶的根（必定是最大的）结点放到数组最后 //将堆最顶的根（必定是最大的）结点放到数组最后 this.swapElement(param, i – 1, 0); //排除处理好的数量 handlerNum++; heapLength = param.length – handlerNum; maxHeap(param, 1, heapLength); } //最后两个元素之间交换 this.swapElement(param, 1, 0); return param;} /** * 交换元素 * * @param param 数组参数 * @param leftIndex 左边索引 * @param rightIndex 右边索引 */private void swapElement(Integer param, int leftIndex, int rightIndex) { Integer oldMaxIndexVal = param; param = param; param = oldMaxIndexVal;}

验证算法

上面我们通过大量图解方式讲解了最大堆排序算法的原理，我们为了更直观的验证算法，现在把全部代码放在一起如下：

/** * <p> * 堆排序算法 * </p> * * @author laizhiyuan * @since 2019/9/20. */public class HeapSortAlgorithm { public static void main(String args) { HeapSortAlgorithm algorithm = new HeapSortAlgorithm(); Integer param = new Integer{6,3,9,8,16,13,2,1}; System.out.println(“排序前：” + JSON.toJSONString(param)); long t = System.currentTimeMillis(); algorithm.heapSortAsc(param); long t2 = System.currentTimeMillis(); System.out.println(“算法耗时：” + (t2 – t) + “ms”); System.out.println(“排序后：” + JSON.toJSONString(param)); } private Integer heapSortAsc(Integer param) { if (param == null || param.length < 1) { return param; } //先自底向上构建最大堆 this.buildMaxHeap(param); //累计处理的数量 int handlerNum = 0; //数组最大下标 int heapLength = param.length; //最后两个下标0,1不用走构建最大堆,直接交换位置即可 int endIndex = 2; for (int i = heapLength; i > endIndex; i–) { //拿出堆最顶的根（必定是最大的）结点放到数组最后 //将堆最顶的根（必定是最大的）结点放到数组最后 this.swapElement(param, i – 1, 0); //排除处理好的数量 handlerNum++; heapLength = param.length – handlerNum; maxHeap(param, 1, heapLength); } //最后两个元素之间交换 this.swapElement(param, 1, 0); return param; } /** * 交换元素 * * @param param 数组参数 * @param leftIndex 左边索引 * @param rightIndex 右边索引 */ private void swapElement(Integer param, int leftIndex, int rightIndex) { Integer oldMaxIndexVal = param; param = param; param = oldMaxIndexVal; } /** * 自底向上构建最大堆 * * @param param 待排序数组参数 */ private void buildMaxHeap(Integer param) { //自底向上构建最大堆, 数组长度的前面一半都是父结点 int parentIndex = param.length / 2; for (int i = parentIndex; i > 0; i–) { //构建最大堆 this.maxHeap(param, i, param.length); } } /** * 构建最大堆必须满足以下要求： * 1、除了根以外的所有结点i都要满足 param[parentIndex(i)] >= param * 2、反过来就是任意父节点值必须大于孩子结点，最顶根父节点值是整颗树的最大值 * * @param param 参数 * @param parentIndex 给定任意父节点索引 * @param heapLength 堆长度(一般就是数组长度) */ private void maxHeap(Integer param, int parentIndex, int heapLength) { //计算左孩子结点数组下标 int leftIndex = leftIndex(parentIndex); //计算右孩子结点数组下标 int rightIndex = rightIndex(parentIndex); //最大值数组下标,默认是父节点 int maxValIndex = parentIndex; //如果左孩子节点值比父节点的值要大，则不满足最大堆要求 //因为下标我们从1开始，所以每次取值减去1保证数组不越界 if (leftIndex <= heapLength && param[leftIndex – 1] > param[parentIndex – 1]) { //这里记录最大值数组下标为左孩子结点 maxValIndex = leftIndex; } //如果右孩子节点值比前面计算得到的最大值要大，则不满足最大堆要求 if (rightIndex <= heapLength && param[rightIndex – 1] > param[maxValIndex – 1]) { //这里记录最大值数组下标为右孩子结点 maxValIndex = rightIndex; } //如果确定父节点的确不是最大值 if (maxValIndex != parentIndex) { //则需要把最大值数组下标位置的值(左或右孩子)交换到父节点下标的位置 Integer oldParentVal = param[parentIndex – 1]; param[parentIndex – 1] = param[maxValIndex – 1]; //交换后，下标为maxValIndex的结点的值是原来父节点的值 param[maxValIndex – 1] = oldParentVal; //经过交换后，以maxValIndex下标作为父节点的子树又可能违反最大堆的性质 //因此这里需要继续递归调用maxHeap maxHeap(param, maxValIndex, heapLength); } } /** * 计算给定下标的父节点的下标 * * @param i 任意给定下标 * @return 父节点的下标 */ private int parentIndex(int i) { return i / 2; } /** * 计算给定下标的左节点的下标 * * @param i 任意给定下标 * @return 左节点的下标 */ private int leftIndex(int i) { return 2 * i; } /** * 计算给定下标的右节点的下标 * * @param i 任意给定下标 * @return 右节点的下标 */ private int rightIndex(int i) { return 2 * i + 1; } }

main方法执行输出如下：

排序前：[6,3,9,8,16,13,2,1]算法耗时：0ms排序后：[1,2,3,6,8,9,13,16]

算法时间复杂度

堆排序算法时间复杂度是O(nlgn)

关于计算算法时间复杂度后面有时间再专门写一篇文章详细说明。

算法适用场景

实际上堆排序算法并不经常被用于排序，大家都知道针对排序有很多钟算法，很多算法效率都比堆排序算法要好，比如平均情况的快排算法。堆排序一般使用场景有优先级计算。比如，作业调度优先级计算就很合适，一般优先级都是根据某个字段在一个集合中计算优先级最高（最大堆）或优先级最低（最小堆）的方式去实现，我们知道，如果仅仅只是计算最大堆或最小堆，我们只需要执行构建堆函数（maxHeap）即可，不需要进行堆排序（heapSort），构建最大堆的时间复杂度是O(lgn)比堆排序的复杂度O(nlgn)效率在给定规模下要高一个常量级别，增长速度方面低线性级别。