1.基本思想
堆排序是一种树型选择排序，是堆直接选择排序的进。
堆是什么：
堆中某个节点的值中是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
完全二叉树是由满二叉树而引用出来的。
除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树称为满二叉树。
如果除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点，这样的二叉树被称为完全二叉树。
通过图解来解释：
此时就将一个无序序列构造成了一个大顶堆
步骤二：将堆顶元素于末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素于末尾元素交换，得到第二大元素。如此反复进行交换，重建，交换。
2）然后重新调整结构，使其继续满足堆定义
3）再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
4）后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
总结：
1）将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆；
2）将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端；
3)重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
2.实例（升序）
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4,6,8,5,9};
heapSort(arr);
}
public static void heapSort(int[] arr){
int temp = 0;
//将无序序列构建成一个堆
for (int i = arr.length / 2 - 1; i >= 0; i--){
adjustHeap(arr, i, arr.length);
}
//调整加交换
for (int j = arr.length - 1; j > 0; j--){
temp = arr[j];
arr[j] = arr[0];
arr[0] =temp;
adjustHeap(arr, 0, j);
}
System.out.println("调整后数组："+ Arrays.toString(arr));
}
public static void adjustHeap(int arr[], int i, int length){
//取出当前元素的值，保存在临时变量中
int temp = arr[i];
//k = i * 2 + 1 k表示是i节点的左子节点
for (int k = i * 2 + 1;k < length; k = k * 2 +1){
//说明左子节点小于右子节点
if(k+1 < length && arr[k] < arr[k+1]){
k++;//k指向右子节点
}
//如果子节点大于父节点
if (arr[k] > temp){
//把较大的值赋给当前节点
arr[i] = arr[k];
i = k;//将 i 指向 k继续循环比较
}else {
break;
}
//当for循环结束后，我们已经将以i为父节点的数的最大值，放在了最顶端（局部）
arr[i] =temp;
}
}
}
3.算法分析
它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为log2i＋1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
所以总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。
空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序是一种不稳定的排序方法
