堆排序是利用二叉树顺序存储结构，通过元素交换来完成排序的算法。每次将最大（最小）元素排到 root 位置，然后将 root 和队尾（下一轮则是和倒数第二个元素交换，以此类推）元素进行交换，并在下一轮忽略队尾元素。
冒泡排序时每轮进行一次线性比较，找出最大值（最小值）；个人理解，堆排序可以类比成树状冒泡排序。
大顶堆：完全二叉树中，所有父节点大等于左右两节点，兄弟节点之间不做要求。
小顶堆：和大顶堆相反，所有父节点都小于左右两节点。
顺序存储二叉树的特点：
- 第n个元素的左子结点为第2*n+1个元素（n从0开始，以下同理）
- 第n个元素的右子结点为第2*n+2个元素
- 第n个元素的父节点为第(n-1)/2个元素
- length/2 - 1就是最后一个非叶子节点的索引
思路：
- 将树调整成大顶堆或小顶堆。升序排列就用大顶堆，降序就用小顶堆。这时根节点就是最大或最小值。
- 将根节点和顺序存储的队尾进行交换。
- 然后将剩余的元素重新构建成一个大顶堆，重复 1、2 就可完成排序
java 实现：
/**
* 堆排序测试
*/
public class HeapSortTest {
public static void main(String[] args) {
int[] input = {2,5,4,89,20,89,6,0,54,78,1};
//1. 第一次构建大顶堆，从最后一个非叶子节点，开始构建子树大顶堆，并依次向上，直到排到根节点
// length/2 - 1就是最后一个非叶子节点的索引
for (int i = input.length/2 - 1; i >=0; i--){// @line14
buildTree(input, i, input.length);
}
PrintUtils.print(input);
//2. 开始交换
//由于上面已经将数组构建成大顶堆，也就是所有子树都已经是大顶堆，但是由于根节点交换，导致根节点不符合大顶堆
//所以每次循环从根节点开始构建大顶堆，然后再交换，循环往复
for (int j = input.length - 1; j > 0; j--){
int temp = input[0];
input[0] = input[j];
input[j] = temp;
buildTree(input, 0, j);
}
PrintUtils.print(input);
}
/**
* 构建大顶堆
* 此方法，用于将第 i 个元素的子树，构建成大顶堆
* @param arr 待排序数组
* @param i 非叶子节点索引
* @param length 构建大顶堆的节点个数
*/
public static void buildTree(int[] arr, int i, int length){
int temp = arr[i];
//第 i 个节点的左子节点索引为 2*i + 1,右子节点的索引为 2*i + 2
//每次循环都是找上个节点的左子节点
for (int k = 2*i + 1; k < length; k = 2*k + 1){
//比较左右节点
if (k + 1 < length && arr[k] < arr[k+1]){
k++;
}
if (arr[k] > temp){
arr[i] = arr[k];
i = k;
}else {
//由 @line14 可知，是从最后一个子树开始构建大顶堆，所以，一旦 arr[k] <= temp，就说明大顶堆构建完成
break;
}
}
arr[i] = temp;
}
}
时间复杂度
- 最优时间复杂度：O(nlog2n)
- 最坏时间复杂度：O(nlog2n)
- 稳定性：不稳定
