9.2.1 堆排序

1. 基本概念

- 堆就是一个完全二叉树（符合从上到下，从左到右的顺序结构）
- 大顶堆
    - 父节点大于子节点
  - 条件：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
- 小顶堆（，父节点小于子节点）
    - 父节点小于于子节点
  - 条件：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

2. 堆排序思想（以升序为例）

1. 构建大顶堆
    1)调整顺序： 从下往上，从右往左 （也就是从后往前）
            从最后一个非叶子节点开始
                    最后一个非叶子节点： i= (arr.length-3)/2
            //    推到过程：
            //       arr[length-1] 是最后一个节点，将其作为右子节点的父节点，就是最后一个非叶子节点
            //       => 2i+2 = length-1
            //       => i = 1/2(length-3)
    2)调整非叶子节点i的步骤：
      - 先将比较两个子节点，得到较大的叶子节点, 让k(k也是索引)指向较大的叶子节点
      - 再将较大的叶子和父节点i比较
      ------如果i大于k, 则以i为祖先节点的树已经满足“大顶堆了”,直接结束,因为下面的之前调整过了
      ------如果i<k, 则互换i和k位置的值(互换后,要考虑互换对其子树的影响)
      ----------继续处理子树：
      --------------i指向k的位置（被换了的元素的位置）, k指向其左子节点2k+1的位置,按上述逻辑继续比较，直到满足父节点满足两个子节点，就不往下了

2. 每构建一次就将堆顶元素（最大元素冒出来，沉到数组最后），然后对剩余的元素继续调整结构，再“沉”

3. 代码实现

public class HeapSortTest {

    /**
     * 功能： 将以为i为祖先节点的子树整成大顶堆
     * @param arr 待调整 arr
     * @param i 当前调整的子树的祖先节点索引 i
     * @param length 表示该数组需要被调整的长度，arr.length 可能大于 length
     */
    public void heapify (int[] arr, int i,int length) {
        // 1.k指向i的左子节点
        for(int k = 2*i+1; k<length;k=2*k+1) {

            // 2.让k指向i的子节点中较大的那个
            if(k+1<length && arr[k] < arr[k+1]) {
                k++;
            }
            // 3.如果 较大的子节点比i大，将i和k 互换
            //      如果换了，需要考虑对k为root节点的子树的结构是否满足“大顶堆”，需要往后处理
            //      如果没换，说明以i为root节点的子树已经满足"大顶堆"了
            int temp = arr[i];
            if(arr[k] > temp) {
                arr[i] = arr[k];
                arr[k] = temp;
                i = k;
            }else {
                // 往下没动的就不用再调整了（之前调整过了）
                break;
            }
        }
    }

    /**
     * 构建大顶对
     * @param arr
     */
    public void buildHeap(int[] arr){
        // 从后往前构建
        for(int i= (arr.length-3)/2; i>=0; i--) {
            heapify(arr,i,arr.length);
        }
    }

    public void heapSort(int [] arr) {
        // 1. 构建大顶堆
        buildHeap(arr);

        // 2. 将堆顶元素（当前最大）沉到数组末尾
        int temp = arr[0];
        arr[0] = arr[arr.length-1];
        arr[arr.length-1] = temp;

        // 对数组length-1 进行重新调整调整堆
        for(int length= arr.length-1;length>0;length--) {
            heapify(arr,0,length);
            temp = arr[0];
            arr[0] = arr[length-1];
            arr[length-1] = temp;
        }
    }

    @Test
    public void test() {
        int[] arr = {1,43,564,22,34,62,5,6,87,45,78,22};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));;
    }
}