【算法】堆排序算法的讲解和代码实践

思路

学习堆排序之前，先简单介绍一下什么是堆。
但是要了解堆，还得先连接二叉树。
二叉树，就是每个节点最多有两个子节点的树形的数据结构。二叉树又有完全二叉树、满二叉树等等，细的就不讲了，可以搜一下资料，还是很多讲这个的。
二叉堆，它是属于完全二叉树，同时它又满足堆的性质（子节点的值总是小于它的父节点（也可以是大于））。也就是说，根节点肯定是最大（也可能是最小）的那个元素。
堆排序就是根据这个特点，把数组看成是一个二叉堆，每次计算出一个最大或最小值然后进行排序的。
那么完全二叉树它怎么跟数组关联上呢？其实完全二叉树它有一个特点，就是它完全可以用数组来表示。详细的这里就不讲了，但是有几点需要记住。

1. 最后一个非叶子节点下标 = 数组长度 ÷ 2 - 1；
2. 非叶子节点的左子节点下标 = 该节点下标 × 2 + 1；
3. 非叶子节点的右子节点下标 = 该节点下标 × 2 + 2。

知道这三点之后，我们就可以根据完全二叉树的性质，把它编程一个二叉堆，然后进行排序了。
关于满二叉树和完全二叉树我还是简单画个图吧，帮助理解。

满二叉树

这种就叫满二叉树，左右完全平衡，非叶子节点都有两个子节点，叶子节点都在一层。
完全二叉树就是说，满二叉树的基础上，比如说要加一个节点，那么只能先在D下面加，然后依次往后。要删除一个节点，只能从右下角开始，先把G删掉，再删F，再删E这样。

完全二叉树

那么完全二叉树跟数组的关系呢？我们加一个数组看一下：

完全二叉树和数组的关系

就可以看到了，比如最后一个非叶子节点是C，下标为2，数组长度是6，6 ÷ 2 - 1 = 2，就印证了上面的公式。

OK二叉树讲的有点多了，下面进入整体，开始将堆排序。

讲解

依然是有这样一个数组：

image.png

那么我们先把它看成一个完全二叉树，开始把它构建成一个最大堆，第一步，找到最后一个非叶子节点，用上面的公式，数组长度为8，最后一个非叶子节点就是 8 ÷ 2 - 1 = 3，那么最后一个非叶子节点就找到了。最后一个非叶子节点前面的元素，都是非叶子节点，我们用蓝色标记出来：

image.png

找到非叶子节点之后，我们从最后一个非叶子节点开始向前遍历所有的非叶子节点。
先看最后一个非叶子节点 -15 ，它是否小于它的两个（也可能是一个）叶子节点。根据公式计算，计算出它的两个叶子下标分别为：3 × 2 + 1 = 7，3 × 2 + 2 = 8，下标为8的元素很显然不存在，那么 -15 只需要跟22对比，明显 -15 小于 22，交换两个元素的位置：

image.png

然后遍历 14，14 的两个子节点下标为 2 × 2 + 1 = 5，2 × 2 + 2 = 6，所以 14 需要与 324 和 1 进行对比，14 比 324 小，交换位置：

image.png

324 与 1 比，324 大，不再交换。
下面轮到 -3。-3 的两个子节点下标为 1 × 2 + 1 = 3，1 × 2 + 2 = 4，-3 与 22、0 对比。-3 小于 22，交换位置：

image.png

22 比 0 大，不再交换。
下一步，26，两个子节点为 1、 2，26 与 22、324 对比。比 22 大，不交换，比 324 小，交换：

image.png

这样就形成了一个最大堆，每一个非叶子节点都大于它自己的叶子节点。最大值就在根节点，也就是我们数组下标为 0 的位置。接下来，我们把最大的数与数组最后一个元素交换位置：

image.png

这样最大的数就跑到了数组的末尾，第一轮的排序也就结束了。
那么第二轮，我们将已排好序的大数排除到构建最大堆的范围之外，只用前面7个数去构件最大堆，构建完成之后，再把最大数挪到下标6的位置，以此类推，即可完成整个数组的排序。

实现

    @Test
    public void heapSort() {
        int[] nums = new int[]{26, -3, 14, -15, 0, 324, 1, 22};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private void sort(int[] nums) {
        // 如果数组长度小于2，直接返回
        if (nums.length < 2) {
            return;
        }
        // 遍历
        for (int i = 0; i < nums.length; i++) {
            // 构建最大堆，nums.length - i 是为了排除掉以排好序的元素
            int lastParentNode = (nums.length - i) / 2 - 1;
            // 遍历所有非叶子节点
            for (int parentNode = lastParentNode; parentNode >= 0; parentNode--) {
                // 如果该节点小于它的左子节点，那么交换位置
                if (nums[parentNode] < nums[parentNode * 2 + 1]) {
                    swap(nums, parentNode, parentNode * 2 + 1);
                }
                // 如果该节点存在右子节点，并且该节点小于它的右子节点，那么交换位置
                if (parentNode * 2 + 2 < nums.length - i && nums[parentNode] < nums[parentNode * 2 + 2]) {
                    swap(nums, parentNode, parentNode * 2 + 2);
                }
            }
            // 构建最大堆完成，把最大的数与堆的最后一个元素交换位置
            swap(nums, 0, nums.length - i - 1);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

image.png