堆排序

二叉堆：

二叉堆是完全二叉树或近似完全二叉树。二叉堆满足两个特性:

（1）父结点的键值总是大于或者等于（小于或者等于）任何一个子节点的键值；

（2）每个结点的左子树和右子树都是一个二叉堆；

当父结点的键值总是大于或者等于任何一个子节点的键值时为大根堆。当父结点的键值总是小于或等于任何一个子节点的键值时为小根堆；

基本思想：

堆的存储：

一般都用数组来表示堆，i结点的父结点下标就为（i-1）/2.它的左右子节点的下标分别为2i+1和2i+2.

堆的插入：

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中

（1）用大根堆排序的基本思想

先将初始数组建成一个大根堆，此堆为初始的无序区；

再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足<=的值；

由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值<=的值，同样要将其调整为堆；

…

直到无序区只有一个元素为止；

总结步骤：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

算法分析：

时间复杂度：

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

应用：

寻找M个数中的前K个最小的数并保持有序；

时间复杂度：O(K)[创建K个元素最大堆的时间复杂度] +（M-K）*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

代码实现：

public class HeapSort {
    //堆排序，从小到大
    public static void main(String[] args) {
        Random random = new Random();
        int[] arr = new int[10];
        for(int i=0;i<arr.length;i++){
            arr[i] = random.nextInt(50);
        }

        //构建大顶堆
        for(int i = (arr.length-1)/2;i>=0;i--){
            adjustHead(arr,arr.length,i);
        }
        System.out.println(Arrays.toString(arr));
        //逐次调整，将堆顶与最后一个元素交换，把大的元素放在后边
        for(int i = arr.length-1;i>0;i--){
            swap(arr,0,i);
            adjustHead(arr,i,0);
        }

        System.out.println(Arrays.toString(arr));
    }

    public static void adjustHead(int[] arr,int size,int index){
        int leftIndex = index*2+1;
        int rightIndex = index*2+2;
        int minIndex = index;
        //如果左边的比较大，就交换
        if(leftIndex < size && arr[leftIndex] > arr[minIndex]){
            minIndex = leftIndex;
        }
        //如果右边比较大，就交换
        if(rightIndex < size && arr[rightIndex] > arr[minIndex]){
            minIndex = rightIndex;
        }
        //交换，并调整子堆
        if(minIndex != index){
            swap(arr,index,minIndex);
            adjustHead(arr,size,minIndex);
        }
    }

    public static void swap(int[] arr, int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
}