2.1.1 堆排序

堆可以理解成用数组实现的完全二叉树结构
完全二叉树中如果每课子树的最大值都在顶部就是大根堆
完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
堆结构的heapInsert与heapify操作
堆结构的增大与减少
优先级队列结构，就是堆结构

public class HeapSort {
    
    public static void sort(int [] arr) {
        if(arr == null || arr.length <2) {
            return;
        }
        
        for(int i=0; i<arr.length;i++) {
                        //从0下标开始逐渐扩充成大根堆
            heapInsert(arr,i);
        }
        int size = arr.length;
        swap(arr,0,--size);
        while(size > 0) {
            heapify(arr,0,size);
            swap(arr,0,--size);
        }
    }
    
    public static void heapInsert(int[] arr, int index) {
        while(arr[index] > arr[(index -1 ) / 2]) {
            swap(arr, index, (index-1)/2);
                        // -0.5 取 0
            index = (index -1)/2;
        }
    }
    //堆化：相当于给根部元素定位置
    public static void heapify(int[] arr, int index, int size) {
        int left = index*2 + 1;//左孩子的下标
        while(left < size) {//下方还有孩子节点

            int largestIndex = left + 1 < size && arr[left + 1] > arr[left] ? left+1 : left;
            
            largestIndex = arr[largest] > arr[index] ? largest : index;

            if(largest == index) {
                break;
            }
            swap(arr, largest,index);
            index = largest;
            left = index * 2 +1;
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

算法流程：
最大堆插入，堆顶为最大值。
交换头尾，数组大小减一，再交换头和尾--的值
依次类推，得到堆排序的结果

堆排序扩展问题：
已知一个几乎有序的数组，几乎有序是指，如果把数组拍好顺序的话，每个元素移动的距离可以不超过K，并且K相对于数组来说比较小，请选择一个合适的排序算法针对这个数据进行排序

public void sortedArrDistanceLessK(int[] arr, int k) {
        //Default is min-heap
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        //build heap size K
        for(; index < Math.min(arr.length, k);index++) {
            heap.add(arr[index]);
        }
        int i =0;
        for(; index < arr.length;i++,index++) {
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        while(!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }