java堆排序

什么是堆排序：图解堆排序
堆排序：利用了堆这种数据结构
堆数据结构：特殊的完全二叉树，因为具有以下的特点:
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就可以了。
堆排序更适合于对部分数据排序吧