什么是堆排序：图解堆排序
堆排序：利用了堆这种数据结构
堆数据结构：特殊的完全二叉树，因为具有以下的特点:
1)每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
2)或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
什么是完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树
完全二叉树和非完全二叉树的区别
右边那个树没有满足
1）第[1~h-1]层结点数达到最大，即所有的父节点都有两个子节点，2这个父节点就只有一个子节点
2）第h层所有节点没有连续集中
堆排序的实现思路：
1)将待排序的数组构造成为一个堆结构，数组为堆结构具有的特点：
大顶堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]
小顶堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]
一般升序采用大顶堆，降序采用小顶堆
2)将堆顶元素和数组末尾元素进行交换
3）重新调整堆结构，继续将堆顶元素和数组末尾元素进行交换，一直重复直到排序完成
代码实现：HeapSort.java
public class HeapSort {
public static void main(String[] args) {
int[] a = {1, 3, 5, 7, 9, 2, 4, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
private static void sort(int[] a) {
//1.构建大顶堆
for (int i = a.length / 2 - 1; i >= 0; i--) {
//从最后一个非叶子节点进行调整
//最后一个非叶子计算方式:a.length/2-1
//依次-1获得父节点自下而上进行调整
adjustHeap(a, i,a.length);
}
//2.交换末尾元素+重新调整堆结构
for (int j = a.length - 1; j> 0;j--) {
//将堆顶元素和末尾元素进行交换
bubbleSort(a, 0, j);
//交换万以后重新调整堆结构
adjustHeap(a, 0, j);
}
}
/**
* 调整堆结构
* @param a 排序的数组
* @param i 待调整的堆顶元素
* @param length 数组长度
* */
private static void adjustHeap(int[] a, int i, int length) {
int temp = a[i]; //取出当前堆顶元素
//从i节点的左节点开始，也就是从2*i+1处
for (int k = 2 * i + 1; k < length; k = k*2 + 1) {
//如果左子节点小于右子节点，k指向右子节点
//a[k]左节点，a[k+1]右节点
if (k + 1 < length && a[k] < a[k+1]) {
k++;
}
//如果子节点大于父节点，则将子节点直接赋给父节点，不进行交换
if (a[k] > temp) {
a[i] = a[k];
i = k;
} else { //不需要进行调整的情况
break;
}
}
a[i] = temp; //将temp放到最终的位置
}
private static void bubbleSort(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
for (int k = 2 * i + 1; k < length; k = k*2 + 1)这层排序是构建堆结构的关键
堆排序的时间复杂度为o(nlogn)
之前面试阿里的时候被问到如果有一百万个数据，如何找到最大的十个数据，当时不知道用什么排序算法，面试官提示堆排序，现在搞清楚了为什么是用堆排序，因为在
for (int j = a.length - 1; j> 0;j--) {
//将堆顶元素和末尾元素进行交换
bubbleSort(a, 0, j);
//交换万以后重新调整堆结构
adjustHeap(a, 0, j);
}
会通过交换元素进行排序，将最大的元素依次放到数组末尾，如果只想得到排序最大的十个数，只要进行十次排序就可以了，即将for循环条件改为a.length-1-10就可以了。
堆排序更适合于对部分数据排序吧
