JAVA十大排序算法之堆排序详解

目录

• 堆排序
• 知识补充
• 二叉树
• 满二叉树
• 完全二叉树
• 二叉堆
• 代码实现
• 时间复杂度
• 算法稳定性
• 思考
• 总结

堆排序

这里的堆并不是JVM中堆栈的堆，而是一种特殊的二叉树，通常也叫作二叉堆。它具有以下特点：

• 它是完全二叉树
• 堆中某个结点的值总是不大于或不小于其父结点的值

知识补充

二叉树

树中节点的子节点不超过2的有序树

满二叉树

二叉树中除了叶子节点，每个节点的子节点都为2，则此二叉树为满二叉树。

完全二叉树

如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左而右。则深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

二叉堆

二叉堆是一种特殊的堆，可以被看做一棵完全二叉树的数组对象，而根据其性质又可以分为下面两种：

• 大根堆：每一个根节点都大于等于它的左右孩子节点，也叫最大堆
• 小根堆：每一个根节点都小于等于它的左右孩子节点，也叫最小堆

如果把一个数组通过大根堆的方式来表示（数组元素的值是可变的），如下：

由此可以推出：

• 对于位置为 k 的节点，其子节点的位置分别为，左子节点 = 2k + 1，右子节点 = 2(k + 1)

如：对于 k = 1，其节点的对应数组为 5

左子节点的位置为 3，对应数组的值为 3

右子节点的位置为 4，对应数组的值为 2

• 最后一个非叶子节点的位置为 (n/2) - 1，n为数组长度

如：数组长度为6，则 (6/2) - 1 = 2，即位置 2 为最后一个非叶子节点

给定一个随机数组[35,63,48,9,86,24,53,11]，将该数组视为一个完全二叉树：

从上图很明显的可以看出，这个二叉树不符合大根堆的定义，但是可以通过调整，使它变为最大堆。如果从最后一个非叶子节点开始，从下到上，从右往左调整，则：

通过上面的调整，该二叉树为最大堆，这个时候开始排序，排序规则：

• 将堆顶元素和尾元素交换交换
• 后重新调整元素的位置，使之重新变成二叉堆

代码实现

public class HeapSort {
    public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};
    public static int[] sort(int[] array) {
        //数组的长度
        int length = array.length;
        if (length < 2) return array;
        //首先构建一个最大堆
        buildMaxHeap(array);
        //调整为最大堆之后，顶元素为最大元素并与微元素交换
        while (length > 0) {//当lenth <= 0时，说明已经到堆顶
            //交换
            swap(array, 0, length - 1);
            length--;//交换之后相当于把树中的最大值弹出去了，所以要--
            //交换之后从上往下调整使之成为最大堆
            adjustHeap(array, 0, length);
        }
        return array;
    }
    //对元素组构建为一个对应数组的最大堆
    private static void buildMaxHeap(int[] array) {
        //在之前的分析可知，最大堆的构建是从最后一个非叶子节点开始，从下往上，从右往左调整
        //最后一个非叶子节点的位置为：array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            //调整使之成为最大堆
            adjustHeap(array, i, array.length);
        }
    }
    /**
     * 调整
     * @param parent 最后一个非叶子节点
     * @param length 数组的长度
     */
    private static void adjustHeap(int[] array, int parent, int length) {
        //定义最大值的索引
        int maxIndex = parent;
        //parent为对应元素的位置（数组的索引）
        int left = 2 * parent + 1;//左子节点对应元素的位置
        int right = 2 * (parent + 1);//右子节点对应元素的位置
        //判断是否有子节点，再比较父节点和左右子节点的大小
        //因为parent最后一个非叶子节点，所以如果有左右子节点则节点的位置都小于数组的长度
        if (left < length && array[left] > array[maxIndex]) {//左子节点如果比父节点大
            maxIndex = left;
        }
        if (right < length && array[right] > array[maxIndex]) {//右子节点如果比父节点大
            maxIndex = right;
        }
        //maxIndex为父节点，若发生改变则说明不是最大节点，需要交换
        if (maxIndex != parent) {
            swap(array, maxIndex, parent);
            //交换之后递归再次调整比较
            adjustHeap(array, maxIndex, length);
        }
    }
    //交换
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

堆的时间复杂度是 O(nlogn)

参考：堆排序的时间复杂度分析

算法稳定性

堆的结构为，对于位置为 k 的节点，其子节点的位置分别为，左子节点 = 2k + 1，右子节点 = 2(k + 1)，最大堆要求父节点大于等于其2个子节点，最小堆要求父节点小于等于其2个子节点。

在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(最大堆)或者最小(最大堆)，这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1，n/2-2，… 1 这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

思考

对于快速排序来说，其平均复杂度为O(nlogn)，堆排序也是O(nlogn)，怎么选择？如下题：

leetcode：数组中的第K个最大元素

此题的意思是对于一个无序数组，经过排序后的第 k 个最大的元素。

我们知道快速排序是需要对整个数组进行排序，这样才能取出第 k 个最大的元素。

如果使用堆排序，且是最大堆的方式，则第k次循环即可找出第 k 个最大的元素，并不需要吧整个数组排序。

所以对于怎么选择的问题，要看具体的场景，或者是两者都可。

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！