算法-堆排序

整体架构流程

大顶推：是构建一个完整的二叉树
大顶推：即父节点的值大于左右子树的值。

循环构建大顶推
在给定的数组，既可以明确树的高度。
在循环的时候，构建树的高度从lgn至0。即从堆低往堆顶构建。
构建过程中：如果左右子树大于父节点，则交互数据后，在调整被交换的节点使其满足大顶推。

提取大顶堆获取排序值
从数组长度(i = a.length-1)至0循环：

1. 交换0和i的值（即大顶堆的跟节点，即最大值）。完成升序排序最大值在数组末尾。
2. 因将i的值替换到0的值位置，需要重新调整大顶堆。且将数组的长度限制小于i。

技术细节

package study.algorithm.sort;

import java.util.Arrays;

/**
 * 堆排序，是先构建一个完整的二叉树
 */
public class HeapSort {

    public static void main(String... args){
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前："+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后："+ Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        builderMaxHeap(arr);
        // 逐个提取堆顶元素（最大值）并调整堆
        // 大顶堆的，最大值的索引是0。
        for (int i = arr.length - 1; i > 0; i--) {
            // 将当前堆顶元素（最大值）与末尾元素交换(即i)
            // 交换完成之后， 大于等于i的索引不参(i至arr.length)与后续大顶堆调整。
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            //调整剩余元素为最大堆，将最大值放在索引为0的位置。
            //指定需要调整的数组长度 i,从0索引位置开始调整大顶对。
            //因上一步，将未尾值换到了索引为0的位置，而索引0的左右子树的值是剩余的最大值。
            maxHeap(arr,i,0);
        }
    }

    /**
     * 构建大顶推，即父节点的值，大于左右子树的值
     */
    public static void builderMaxHeap(int[] arr) {
        int n = arr.length;
        for (int i = n / 2; i >= 0; i--) {
            maxHeap(arr, n, i);
        }
    }

    /**
     * 构建大顶推，即父节点的值，大于左右子树的值
     *
     * @param arr 数组
     * @param n   需要调整整个数组的长度
     * @param i   父节点索引位置
     */
    public static void maxHeap(int[] arr, int n, int i) {
        //最大值索引默认为i，i的左右子树在数组中索引的位置
        int largest = i;
        int right = 2 * i + 1;
        int left = 2 * i + 2;
        //如果左子树索引不越界(即存在左子树)，且左子树的值大于，最大值索引的值
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        //如果右子树索引不越界(即存在右子树)，且右子树的值大于，最大值索引的值
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        //说明父节点的值，小于左右子树的值
        //1. 调整堆的最大值位于父节点
        //2. 因左右子树的值，存在修改则需要调整当前修改节点的堆，满足大顶堆
        if (i != largest) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            maxHeap(arr, n, largest);
        }
    }
}

小结

构建大顶堆是从堆低往堆顶开始构建
每次获取大顶堆最大的值，完成排序