堆排序

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        int[] arr = {1,3,9,6,5,4,7,2,8};

        // 打印排序前的数组
        System.out.println(Arrays.toString(arr));

        // 执行堆排序操作
        heapSort(arr);

        // 打印排序后的数组
        System.out.println(Arrays.toString(arr));

        return null;
    }

    public static void heapSort(int[] arr){

        // 1、将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
        for(int i = arr.length / 2 - 1 ; i >= 0 ; i-- ){

            //从第一个非叶子节点从下至上，从后向前调整结构
            adjustHeap( arr , i , arr.length );

        }

        // 2、将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端，此时数组末端存储了当前区间最大的元素
        for(int j = arr.length - 1 ; j > 0 ; j-- ){

            // 3、每次将堆顶元素与末尾元素进行交换，使末尾元素最大
            swap(arr,0,j);

            // 4、重新对堆进行调整
            adjustHeap(arr,0,j);

            // 执行完 4 之后，剩下未排序的那些元素依旧维护着一个最大堆，继续下一轮循环
        }

    }

    // 调整大顶堆
    public static void adjustHeap(int []arr,int parent,int length){

        // 1、取出当前元素，需要把它挪到正确的位置上，比如此时是 A 元素
        //       A
        //     /   \
        //    B     C
        int temp = arr[parent]; 

        // 2、从 parent 节点的左子节点开始
        // 也就是 2 * parent + 1 处开始
        int child = 2 * parent + 1 ;


        while(child < length){

            //       A
            //     /   \
            //    B     C
            // 获取 A 、B 、C 三者的最大值，把它放到 A 位置
            // 于是，第一步先去对比 B 和 C，查看它们的较大值是哪一个
            // 3、如果左子节点小于右子节点，child 指向右子节点
            if( child + 1 < length && arr[child] < arr[ child + 1 ] ){
                child++;
            }

            // 如果父节点的值已经大于孩子节点的值，说明在正确位置上
            // 直接结束
            if (temp >= arr[child]){
                break;
            }

            // B 、 C 都是 A 的子节点，如果 B 、 C 的较大值大于 A
            // 将最大值赋值给 A
            arr[parent] = arr[child];

            // 此时，parent 这个节点已经存放了正确的元素
            //       B
            //     /   \
            //    B     C
            // 接下来，需要观察一下，parent 原先的节点值 A 应该放到哪个位置
            // 所以，顺着 parent 这个节点来到它的子节点，就是 B 这个节点的位置，也是 child 这个节点的位置
            parent = child;

            // 那么，子节点也发生了变化，从它的左子节点开始
            child = 2 * parent + 1;

        }

        // 将 temp 值放到最终的位置
        arr[parent] = temp;
    }

    // 交换元素
    public static void swap(int []arr,int a ,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

时间复杂度

堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。

当想得到一个序列中第 k 个最小的元素之前的部分排序序列，最好采用堆排序。

TopK 系列问题

因为堆排序的时间复杂度是O(n+klogn)，若k≤n/logn，则可得到的时间复杂度为O(n)。

算法稳定性

堆排序是一种不稳定的排序方法。

因为在堆的调整过程中，对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

程序员吴师兄算法训练营永久会员

收藏 海报 链接