一、堆相关概念

1.堆

堆是完全二叉树，即除最后一层外，其它层都是满的，且最后一层从左到右依次都有元素。如下图所示。

堆是用数组来实现的，图中下标就为数组的下标，其对应数组[5, 1, 7, 2, 8, 6, 3, 9, 4]，可以看出节点i的左子节点对应2i+1节点，右子节点为2i+2，父节点为(i-1)/2。

2.大顶堆与小顶堆

大顶堆：若堆中每个非叶子节点的值均大于等于其子节点的值，则称这个堆为大顶堆。

小顶堆：若堆中每个非叶子节点的值均小于等于其子节点的值，则称这个堆为小顶堆。

大顶堆与小顶堆对左右子节点值的大小没有要求。

二、堆排序的基本思想

1.根据大顶堆和小顶堆的概念，可知它们的根节点对应整个堆最大值与最小值。

2.将长度为n的待排序数组调节成大顶堆（或小顶堆），将数组头元素与末尾元素互换，最大值（最小值）就放在了最后。

3.继续将数组的前n-1位调成大顶堆（或小顶堆），将数组头元素与第n-1个元素互换，将次大值（次小值）放在对应位置，按此方法，一直循环调节与互换，直到待调节元素为1个。

4.最后将得到升序（降序）的数列。

三、代码实现分析

1.将堆调节成大顶堆（以大顶堆为例）

(1) 方法概述

一个堆调节成大顶堆的过程是比较复杂的。
函数：这里定义一个函数，该函数可以将以堆中某个非叶子节点为根节点的子树调节成大顶堆（只是部分为大顶堆）。

思路：从最后一个叶子节点开始调节，接着调节这个节点的前一个节点（即数组中的前一个元素，且最后一个非叶子节点的前面都是非叶子节点），直到调节到整个堆根节点（即数组头元素）。
优点：这样可以保证每次调节节点时，该节点的左右子树都是大顶堆。

要点：调节该非叶子节点i，就是将其与左右子节点中的最大值放在该节点，此处若该节点为最大值，则以该节点为根节点的树就是大顶堆，不用进行调整。若该节点不为最大值，则会与左右子节点中最大值发生互换，这可能会影响左右子树是否还为大顶堆，此时需要进一步调整左右子树，调整方法与前面相同。直到调整到叶子节点，此时以非叶子节点i为根节点的树，就成为了大顶堆。

堆中最后一个非叶子节点的索引：arr.length/2 - 1。

(2) 图解

以arr = [5, 1, 7, 2, 8, 6, 3, 9, 4]为例：

arr.length/2 - 1 = 3，第一个飞叶子节点索引为3。交换后：

调整索引为2的：不变

调整索引为1的：

这里左子树因互换而不满足大顶堆，需调整：

调节索引为0的：

调节其左子树：

索引为4的是叶子节点，结束调整。
调节完索引为0的节点，调节结束，大顶堆形成。

(3) 代码

调节节点函数：

/*** 将以i为根节点对应的树调节成大顶堆* @param arr 待调整的数组* @param i 非叶子节点在数组中的位置* @param length 表示待调整树的长度（越来越小）** 第i节点的左子节点为【2*i+1】，右子节点为【2*i+2】*/public static void adjustHeap(int[] arr, int i, int length) {int temp = arr[i];//先取出当前元素的值，保存在临时变量//开始调整for (int index = i * 2 + 1; index < length; index = index * 2 + 1) {if (index + 1 < length && arr[index] < arr[index + 1]) {//找左子节点和右子节点的最大值index++;}if (arr[index] > temp) {//子节点大于当前节点的值arr[i] = arr[index];arr[index] = temp;i = index;//i指向index，继续循环比较，调整成大顶堆} else {break;}}}public static void main(String[] args){int[] arr = {5, 1, 7, 2, 8, 6, 3, 9, 4};//将整个堆调成大顶堆for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length);}}

2.堆排序算法

1.直接嵌套循环（不推荐）

 public static void heapSort(int[] arr){System.out.println("堆排序");for(int length = arr.length;length > 1;length--){//调节成大顶堆for(int i = length/2-1;i>=0;i--){adjustHeap(arr, i ,length);}int temp = arr[0];arr[0] = arr[length - 1];arr[length - 1] = temp;}}

调节完成后，进行交换，再调节的短一个的数组（length–），此种方法容易理解，但耗时很大。

2.从0开始调节
我们注意到从第二次开始调节开始（下图为第二次调节开始时），根节点的左右子树都满足大顶堆的概念，无需进行从下至上的排序，直接从根节点开始调节即可。

代码：

    public static void heapSort(int[] arr){int temp;//将树调成大顶堆for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length);}//从0开始反复调节for (int k = arr.length - 1; k > 0; k--) {temp = arr[0];arr[0] = arr[k];arr[k] = temp;adjustHeap(arr, 0, k);}}

四、完整代码

public class HeapSort {public static void main(String[] args) {int[] arr = {5, 1, 7, 2, 8, 6, 3, 9, 4};heapSort(arr);System.out.println(Arrays.toString(arr));}public static void heapSort(int[] arr){int temp;//将树调成大顶堆for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length);}for (int k = arr.length - 1; k > 0; k--) {temp = arr[0];arr[0] = arr[k];arr[k] = temp;adjustHeap(arr, 0, k);}}public static void adjustHeap(int[] arr, int i, int length) {int temp = arr[i];//先取出当前元素的值，保存在临时变量//开始调整for (int index = i * 2 + 1; index < length; index = index * 2 + 1) {if (index + 1 < length && arr[index] < arr[index + 1]) {//找左子节点和右子节点的最大值index++;}if (arr[index] > temp) {//子节点大于当前节点的值arr[i] = arr[index];arr[index] = temp;i = index;//i指向k，继续循环比较，调整成大顶堆} else {break;}}}
}