大根堆以及堆排序

直接上代码

private static void sortMaxHeap(int[] arr) {//大根堆排序
    if (arr==null || arr.length < 2) {
        return;
    }
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i >= 0; i--) {
        swap(arr, 0, i); //将最大根换到最后
        adjustMaxHeap(arr, i, 0); //调整大根堆，除了最后已经排好序的元素
    }
}

private static void buildMaxHeap(int[] arr) {//构造一个大根堆
    if (arr==null || arr.length < 2) {
        return;
    }
    for (int i = arr.length/2 - 1; i >= 0; i--) {//从所有叶子节点的父节点开始调整
        adjustMaxHeap(arr, arr.length, i);
    }
}

private static void adjustMaxHeap(int[] arr, int size, int i) {//调整索引为i的子树，使子树是一个大顶堆。
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int max = i; //最大值的索引，默认为父节点
    if (left < size && arr[left] > arr[max]) { //左子节点与父节点比大小
        max = left;
    }
    if (right < size && arr[right] > arr[max]) { //右子节点与父节点比大小
        max = right;
    }
    if (max != i) { //最大点是子节点
        swap(arr, max, i); //与子节点交换位置
        adjustMaxHeap(arr, size, max); //因为子节点发生了改变，要调整子节点
    }
}

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

public static void main(String[] args) {
    int[] arr = new int[]{1,22,55,88,44,996,44,66,15,700};
    buildMaxHeap(arr);//结果[996, 700, 55, 88, 44, 1, 44, 66, 15, 22]
    System.out.println("arr = " + Arrays.toString(arr));
    sortMaxHeap(arr);//结果[1, 15, 22, 44, 44, 55, 66, 88, 700, 996]
    System.out.println("arr = " + Arrays.toString(arr));
}

• 首先去了解二叉树，然后想象数组也可以是一个二叉树。
• 假设索引0是根节点，左子节点是索引1，右子节点是索引2
• 索引1的左子节点是索引3，右子节点是索引4；索引2的左子节点是索引5，右子节点是索引6
• 以此类推，如果根节点是索引n，那么左子节点的索引是2*n+1，右子节点是2*n+2

• 这时我们有了一个堆了，而大根堆就是子树的根都是树中的最大值
  一张图可以更好理解大根堆：

  
  大根堆示意图.png
• 再来说堆排序，假如此时我们已经有了一个大根堆了，那么我们把根与堆的最后一个节点进行交换，如上图20与9交换
• 确定了最后一个索引位的值，然后将3之前的节点调整为新的大根堆，就又得到了一个大根堆，与第一步同理
• 以此类推，最后就得到一个排好序的数组