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

思路

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

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

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

满二叉树

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

完全二叉树

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

完全二叉树和数组的关系

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

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

讲解

依然是有这样一个数组:

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

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

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

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

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

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

这样最大的数就跑到了数组的末尾,第一轮的排序也就结束了。
那么第二轮,我们将已排好序的大数排除到构建最大堆的范围之外,只用前面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 = 0; parentNode--) {
                // 如果该节点小于它的左子节点,那么交换位置
                if (nums[parentNode]

未经允许不得转载:窗外天空 » 【算法】堆排序算法的讲解和代码实践

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址