堆排序 - 简书

实现须知

最大堆的性质
- 堆是特殊的完全二叉树
- 所有父节点的值都比其子节点的值大
- 堆顶是最大元素
堆化一个节点
- 使该父节点与其子节点中值最大的节点位于该父节点的位置
- 也即如果有个子节点是这三个节点(一父两子)中最大的，则交换该节点与父节点的位置
- 上述步骤(交换两个节点的位置)可能导致新的子节点(原来的父节点被交换下去变成新的子节点)作为父节点时不满足最大堆的条件，于是再以它为父节点重复上述步骤，直至到达树的末端
堆化一棵完全二叉树
- 从最后一个父节点开始堆化，然后堆化倒数第二个父节点，倒数第三个………直到堆化堆顶节点
本文实现方法是利用最大堆的性质"升序"排序，并且基于数组以及索引的，所以并没有真正的完全二叉树类和节点类

算法思路

将要排序的序列看成二叉树并堆化
将堆顶元素与最后一个元素交换，此时最大元素就换到了最后
将堆顶节点堆化
重复步骤：
- 交换
  要注意最大的元素已经被交换到最后，所以每次交换的时候，"最后一个元素"是上一次的前一个
- 堆化堆顶节点

算法实现

具体方法

将交换数组元素的方法void swap(int[], int, int)进行封装

    /**
     * 交换数组中的两个数
     *
     * @param nums 要交换值的数组
     * @param i    第一个索引
     * @param j    第二个索引
     * @return void
     */
    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

堆化一个节点void nodeHeapify(int[] tree, int index, int N)
参数N是当前需要堆化的元素个数
- 记录最大值索引(假定父节点是最大值)，用于递归
- 记录左右子节点索引
  - 左子节点索引 = (父节点索引 * 2) + 1leftIndex = (index * 2) + 1
  - 右子节点索引 = (父节点索引 * 2) + 2rightIndex = (index * 2) + 2
- 分别判断左右子节点索引是否越界，再更新最大值索引
- 如果最大值索引不是父节点索引，则交换父节点索引与最大值索引的值，然后递归堆化nodeHeapify(tree, maxIndex, N)

    /**
     * 使某个节点与他的子节点符合最大堆的性质
     *
     * @param tree  要进行排序的树(以数组形式)
     * @param index 要堆化的节点索引
     * @param N     树的节点数
     * @return void
     */
    public static void nodeHeapify(int[] tree, int index, int N) {
        // 找出index索引节点与它的子节点中最大的节点
        // 记录最大值节点的索引, 用于递归
        int maxIndex = index;
        // 找出左右子节点的索引
        int leftIndex = (index * 2) + 1;
        int rightIndex = (index * 2) + 2;
        // (索引不越界情况下)如果左子节点值大于最大值
        if (leftIndex < N && tree[leftIndex] > tree[maxIndex]) {
            // 更新最大值索引
            maxIndex = leftIndex;
        }
        // (索引不越界情况下)如果右子节点值大于最大值
        if (rightIndex < N && tree[rightIndex] > tree[maxIndex]) {
            // 更新最大值索引
            maxIndex = rightIndex;
        }
        // 如果父节点不是三个节点中最大的
        if (index != maxIndex) {
            // 则交换最大值索引与父节点索引的值(此时三个节点以满足最大堆的特性)
            swap(tree, index, maxIndex);
            // 但是刚才与父节点交换的节点, 可能它与它的子节点因为这次交换而不满足最大堆特性
            // 递归, 对刚才被交换的最大值索引的节点进行堆化
            nodeHeapify(tree, maxIndex, N);
        }
    }

堆化一棵完全二叉树
- 从最后一个父节点lastParentIndex = (N - 1 - 1) / 2开始堆化
  - 最后一个节点索引N - 1
  - 节点的父节点索引(index - 1) / 2(舍去余数)
- 然后堆化倒数第二个节点，依次往上走for (int i = lastParentIndex; i >= 0; i--)

    /**
     * 将整个完全二叉树堆化(每个节点堆化)
     *
     * @param tree 要堆化的树
     * @param N    树的节点数
     * @return void
     */
    public static void treeHeapify(int[] tree, int N) {
        // 从最后一个父节点开始, 往前走, 堆化每个父节点
        int lastParentIndex = (N - 1 - 1) / 2;
        for (int i = lastParentIndex; i >= 0; i--) {
            nodeHeapify(tree, i, N);
        }
    }

堆排序主体void heapSort(int[], int)
- 首先堆化整棵树
- 循环执行for (int i = N - 1; i > 0; i--)交换堆顶和最后一个元素，堆化堆顶元素，i == 0时所有元素已经排序好
- 注意：每次最后一个元素是上次一次最后一个元素的前一个，所以每次堆化堆顶元素的时候，把堆的大小当作较少了1，于是传进去的参数N = i(i从N - 1递减到0)

    /**
     * 堆排序: 将树堆化之后, 依次取出堆顶的值, 重新堆化, 直到取出所有值
     *
     * @param tree 要排序的数组
     * @param N    树的节点数
     * @return int[] result 排序后的数组
     */
    public static void heapSort(int[] tree, int N) {
        // 将树堆化
        treeHeapify(tree, N);
        // 依次取出堆顶(将最后一个节点与堆顶的值对换), 堆化堆顶节点
        for (int i = N - 1; i > 0; i--) {
            // 堆顶是最大值, 将堆顶与最后一个节点值交换
            // 每循环一次, 虽然数组大小不变, 但因为每次都取出堆顶所以堆的"大小" - 1
            swap(tree, 0, i);
            // 堆化堆顶节点(注意每次循环堆的的大小N - 1, 所以参数N = i)
            nodeHeapify(tree, 0, i);
        }
    }

测试

    public static void main(String[] args) {
        int[] nums = {1, 4, 7, 5, 2, 6, 3, 8, 9, 1, 4, 7, 8, 5, 2, 3, 1, 4};
        System.out.println(Arrays.toString(nums));
        heapSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

排序前：[ 1, 4, 7, 5, 2, 6, 3, 8, 9, 1, 4, 7, 8, 5, 2, 3, 1, 4 ]
排序后：[ 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9 ]

完整代码

public class HeapSortDemo {
    public static void main(String[] args) {
        int[] nums = {1, 4, 7, 5, 2, 6, 3, 8, 9, 1, 4, 7, 8, 5, 2, 3, 1, 4};
        System.out.println(Arrays.toString(nums));
        heapSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 交换数组中的两个数
     *
     * @param nums 要交换值的数组
     * @param i    第一个索引
     * @param j    第二个索引
     * @return void
     */
    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    /**
     * 使某个节点与他的子节点符合最大堆的性质
     *
     * @param tree  要进行排序的树(以数组形式)
     * @param index 要堆化的节点索引
     * @param N     树的节点数
     * @return void
     */
    public static void nodeHeapify(int[] tree, int index, int N) {
        // 找出index索引节点与它的子节点中最大的节点
        // 记录最大值节点的索引, 用于递归
        int maxIndex = index;
        // 找出左右子节点的索引
        int leftIndex = (index * 2) + 1;
        int rightIndex = (index * 2) + 2;
        // (索引不越界情况下)如果左子节点值大于最大值
        if (leftIndex < N && tree[leftIndex] > tree[maxIndex]) {
            // 更新最大值索引
            maxIndex = leftIndex;
        }
        // (索引不越界情况下)如果右子节点值大于最大值
        if (rightIndex < N && tree[rightIndex] > tree[maxIndex]) {
            // 更新最大值索引
            maxIndex = rightIndex;
        }
        // 如果父节点不是三个节点中最大的
        if (index != maxIndex) {
            // 则交换最大值索引与父节点索引的值(此时三个节点以满足最大堆的特性)
            swap(tree, index, maxIndex);
            // 但是刚才与父节点交换的节点, 可能它与它的子节点因为这次交换而不满足最大堆特性
            // 递归, 对刚才被交换的最大值索引的节点进行堆化
            nodeHeapify(tree, maxIndex, N);
        }
    }

    /**
     * 将整个完全二叉树堆化(每个节点堆化)
     *
     * @param tree 要堆化的树
     * @param N    树的节点数
     * @return void
     */
    public static void treeHeapify(int[] tree, int N) {
        // 从最后一个父节点开始, 往前走, 堆化每个父节点
        int lastParentIndex = (N - 1 - 1) / 2;
        for (int i = lastParentIndex; i >= 0; i--) {
            nodeHeapify(tree, i, N);
        }
    }

    /**
     * 堆排序: 将树堆化之后, 依次取出堆顶的值, 重新堆化, 直到取出所有值
     *
     * @param tree 要排序的数组
     * @param N    树的节点数
     * @return int[] result 排序后的数组
     */
    public static void heapSort(int[] tree, int N) {
        // 将树堆化
        treeHeapify(tree, N);
        // 依次取出堆顶(将最后一个节点与堆顶的值对换), 堆化堆顶节点
        for (int i = N - 1; i > 0; i--) {
            // 堆顶是最大值, 将堆顶与最后一个节点值交换
            // 每循环一次, 虽然数组大小不变, 但因为每次都取出堆顶所以堆的"大小" - 1
            swap(tree, 0, i);
            // 堆化堆顶节点(注意每次循环堆的的大小N - 1, 所以参数N = i)
            nodeHeapify(tree, 0, i);
        }
    }
}