二叉堆实现

以下为最小堆代码

/**
 * 用例适用于  '最小堆'
 */
public class 二叉堆 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        upAdjust(arr);
        System.out.println(Arrays.toString(arr));

        arr = new int[]{9, 6, 7, 11, 66, 5, 2, 3, 1, 0};
        build(arr);
        System.out.println(Arrays.toString(arr));

    }
    
    ------------------------------------------------------------
    打印结果
    [0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
    [0, 1, 2, 3, 6, 5, 7, 9, 11, 66]
    ------------------------------------------------------------
    

    /**
     * 上浮调整
     */
    public static void upAdjust(int[] arr) {
        int childIndex = arr.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        // temp 用于保存插入的叶子节点值, 用于最后的赋值
        int temp = arr[childIndex];
        while (childIndex > 0 && temp < arr[parentIndex]) {
            // 无需真正交换, 单项赋值即可
            arr[childIndex] = arr[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        arr[childIndex] = temp;
    }

    /**
     * 下沉调整
     *
     * @param arr         要调整的堆
     * @param parentIndex 要 '下沉' 的父节点
     * @param length      堆的有效大小
     */
    public static void downAdjust(int[] arr, int parentIndex, int length) {
        // temp 用于保存插入的叶子节点值, 用于最后的赋值
        int temp = arr[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < length) {
            // 如果有右节点, 且右节点小于左节点的值, 则定位到右节点
            if (childIndex + 1 < length && arr[childIndex + 1] < arr[childIndex]) {
                childIndex++;
            }
            // 如果父节点小于子节点的值则跳出, 不需要调整
            if (temp < arr[childIndex]) {
                break;
            }

            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;

        }
        arr[parentIndex] = temp;
    }

    /**
     * 构建二叉堆
     * <p>
     * 二叉堆本质上是完全二叉树, 但是存储方式不是链式存储, 而是顺序存储, 所用数据结构为数组
     */
    public static void build(int[] arr) {
        // 从最后一个非叶子节点开始, 依次做'下沉'调整
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }

    }


}

堆排序

public class 堆排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};

        sort(arr);
    }

    public static void sort(int[] arr) {
        二叉堆.build(arr);
        System.out.println(Arrays.toString(arr));

        for (int i = arr.length - 1; i >= 0; i--) {
            // 最后一个元素和第一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            二叉堆.downAdjust(arr,0,i);
            System.out.println(Arrays.toString(arr));
        }
    }
}

排序结果

[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
[1, 3, 2, 6, 5, 7, 8, 9, 10, 0]
[2, 3, 7, 6, 5, 10, 8, 9, 1, 0]
[3, 5, 7, 6, 9, 10, 8, 2, 1, 0]
[5, 6, 7, 8, 9, 10, 3, 2, 1, 0]
[6, 8, 7, 10, 9, 5, 3, 2, 1, 0]
[7, 8, 9, 10, 6, 5, 3, 2, 1, 0]
[8, 10, 9, 7, 6, 5, 3, 2, 1, 0]
[9, 10, 8, 7, 6, 5, 3, 2, 1, 0]
[10, 9, 8, 7, 6, 5, 3, 2, 1, 0]
[10, 9, 8, 7, 6, 5, 3, 2, 1, 0]