堆排序（Java）

aruba

发布于 2021-12-06 17:14:29

3880

发布于 2021-12-06 17:14:29

文章被收录于专栏：android技术

堆排序：堆排序的思想比较难理解，首先将数据看成是一个二叉树，对数据进行二叉树的建立（建堆），这个过程也是排序的过程，将最小或最大的值排到根节点上，如果采用最大值，则称为最大堆，反之，称为最小堆例如：有一个数组为[8,1,4,2,3],将他变为二叉树为：

        8
    1     4
2    3

要对它进行排序，可以从8开始，和他的左孩子和右孩子比较，将小的那个和本身进行替换，第一次替换变为：

        1
    8     4
2    3

再以替换的节点作为父节点，和他的左孩子和右孩子比较，将小的和本身那个交换

        1
    2     4
8    3

另外我们观察索引发现，当前节点索引 * 2 + 1即为左孩子的索引，当前节点索引 * 2 + 2即为右孩子索引实现代码：

    /**
     * 建堆
     *
     * @param nums
     * @param size
     * @param index
     */
    private void createHeap(int[] nums, int size, int index) {
        //数组索引：0 1 2 3 4 5 6
        //0的左孩子索引是1 ，0的右孩子索引是2
        //1的左孩子索引是3，右孩子是4
        //2的左孩子索引是5，右孩子是6
        //得出：
        int leftIndex = 2 * index + 1;//左孩子索引
        int rightIndex = leftIndex + 1;//右孩子索引

        //将当前节点、左孩子、右孩子的值进行比较，较小的值和当前节点替换
        if (leftIndex >= size && rightIndex >= size) {//没有孩子，不用处理了
            return;
        }

        int currentValue = nums[index];
        int leftValue = leftIndex < size ? nums[leftIndex] : Integer.MAX_VALUE;//可能没有（代码走到这，左孩子其实不可能没有）
        int rightValue = rightIndex < size ? nums[rightIndex] : Integer.MAX_VALUE;//可能没有

        if (currentValue <= leftValue && currentValue <= rightValue) {//当前节点已经小了，不用处理
            return;
        }

        if (leftValue < rightValue) {//左孩子替换当前节点
            nums[index] = leftValue;
            nums[leftIndex] = currentValue;
            createHeap(nums, size, leftIndex);
        } else {//右孩子替换当前节点
            nums[index] = rightValue;
            nums[rightIndex] = currentValue;
            createHeap(nums, size, rightIndex);
        }
    }

但是我们发现自上而下建立二叉树，是不可行的比如：数组为：[8,2,4,1,3] 二叉树为：

        8
    2     4
3    1

那么调用我们代码后形成的树为：

        2
    1     4
3    8

最小值1，并没有到达根节点，这时转变思路，不用从根节点开始建立，而是从树的底部开始建立堆，过程为：先将1，2，3进行排序

        8
    1     4
3    2

然后1，4，8进行排序

        1
    8     4
3    2

思想就是从最深度- 1的深度的倒数第一个节点开始倒着建堆，以上面的数据就是从4开始，由于是完全二叉树，所以索引为：(数组大小 - 1) / 2 实现代码：

    /**
     * 自下而上建堆
     *
     * @param nums
     */
    public void buildHeap(int[] nums) {
        for (int i = (nums.length - 1) / 2; i >= 0; i--) {
            createHeap(nums, nums.length, i);
        }

        //取出最小的
        int n = nums.length;
        while (n > 0) {
            System.out.print(nums[0] + " ");
            nums[0] = nums[n - 1];
            n--;
            createHeap(nums, n, 0);
        }
    }

测试代码：

        int[] nums = new int[]{5, 7, 1, 3, 9, 0, 1, 6, 8, 4};
        buildHeap(nums);

结果： 0 1 1 3 4 5 6 7 8 9 堆排序本身用来排序性能并不高，但是作为查找的时候性能很高，由于二分查找只针对已经排好序的顺序表，对于大数据量的散列表，推排序就可以出场了，因为推排序的建堆过程，尽可能少的访问节点，减少了对一个节点的重复访问，而又具有二分的思想，相比于其他排序，查找性能非常高

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/8/18 上，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树