（1）完全二叉树的概念：前h-1层为满二叉树，最后一层连续缺失右结点！（标注：大根堆为升序，小根堆为降序）
（2）首先堆是一棵全完二叉树，排序思路：
a:构建一个堆分为两步：
1）创建一棵完全二叉树 2）调整为一个堆
b:算法描述：
① 创建一棵完全二叉树
② while(有双亲){
A:调整为大根堆；
B:交换根和叶子结点；
C:砍掉叶子结点；
}
c:时间复杂度为 O(nlogn) ,空间复杂度为 O(1), 是不稳定排序！
（3）代码实现
/**
* @auther yangchao
* @date 2019/7/31
*/
/*堆排序思想：【完全二叉树的定义：前 h-1 层为满二叉树，最后一层连续缺失右节点（大根堆升序排列，小根堆降序排列）】
首先堆是一棵完全二叉树，根据数组下标就可建成了一棵完全二叉树
其次：while(有双亲) {
A: 调整为一个大根堆 【adjust()函数实现】
B: 交换最后一个叶子结点和根结点 【swap()函数实现】
C: 砍掉最后一个叶子结点 【即元素个数 n--】
}
*/
public class HeapSort {
//初始化数组，类型为引用包装类型 Integer
private static final Integer[] array = {2, 4, 6, 1, 3, 8, 7, 10, 9, 5};
//初始化数组的长度
private static Integer length = array.length;
/**
* 交换数组元素
*/
private static void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* 调整大根堆
*/
private static void adjust() {
int parent; //记录双亲节点
Boolean flag = true; //记录已经调整好为大根堆判定
while(flag) {
parent = (length - 2) / 2; //记录最后一个双亲节点
flag = false;
while(parent >= 0) { //确保有双亲结点
if (array[parent] < array[2 * parent]) { //若根结点大于左子女结点，就交换
swap(parent, 2 * parent);
flag = true;
}
if (2 * parent + 2 < length && array[parent] < array[2 * parent + 1]) { //若存在右子女，并且根结点大于右子女结点，就交换
swap(parent, 2 * parent + 1);
flag = true;
}
parent = parent - 1;
}
}
}
/**
* 堆排序
*/
private static void heapSort() {
while(length > 2){ //保证有双亲结点
adjust(); //调整大根堆函数
swap(0, length - 1); //将最后一个叶子结点和根结点交换
length = length - 1; //砍掉最后一个叶子
}
}
public static void main(String[] args) {
heapSort();
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
（4）排序结果：
每天进步一点点，加油，亲爱的自己......