堆排序：力扣215.数组中的第K个大元素

一、问题描述

在一个整数数组 nums 中，需要找出第 k 个最大的元素。这里要注意，我们要找的是数组排序后的第 k 个最大元素，而不是第 k 个不同的元素。例如，对于数组 [3,2,1,5,6,4]，当 k = 2 时，第 2 个最大的元素是 5。

二、解决思路

我们可以使用大顶堆排序算法来解决这个问题。大顶堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。通过构建大顶堆，我们可以将数组中的元素按照从大到小的顺序排列，然后取出第 k 个元素即可。

三、代码实现

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let n = nums.length;

    // 以大顶堆为做法，其实堆就只是通过完全二叉树的性质，在数组中进行操作
    // 如果数组以 0 开头，那么节点 i 的左节点为 2 * i + 1，右节点为 2 * i + 2
    // max 表示维护的是 0 到 max 这部分的顺序，max 到 n - 1 这部分已经形成顺序了
    // i 表示维护的是以 i 为父节点，它和它子节点的大顶堆关系
    function heapify(max, i) {
        let lastMax = i;
        let lson = 2 * i + 1;
        let rson = 2 * i + 2;

        // 比较左子节点和父节点的大小，如果左子节点更大，则更新 lastMax
        if (lson < max && nums[lson] > nums[lastMax]) {
            lastMax = lson;
        }

        // 比较右子节点和当前最大节点的大小，如果右子节点更大，则更新 lastMax
        if (rson < max && nums[rson] > nums[lastMax]) {
            lastMax = rson;
        }

        // 如果 lastMax 不等于 i，说明需要交换父节点和最大子节点的位置
        if (lastMax != i) {
            let temp = nums[lastMax];
            nums[lastMax] = nums[i];
            nums[i] = temp;

            // 递归调用 heapify 函数，继续维护以 lastMax 为根节点的子树的大顶堆性质
            heapify(max, lastMax);
        }
    }

    // 大顶堆排序的入口
    function heap_sort() {
        // 首先要从最后一个非叶子节点开始建立大顶堆
        for (let i = Math.floor(n / 2 - 1); i >= 0; i--) {
            heapify(n, i);
        }

        // 然后呢，我们已经形成大顶堆了，现在要把他们完全排序
        // 怎么做呢，先把 [0] 与 [n - 1] 对调，这样 [n - 1] 的数就变成了最大的数
        // 接下来再维护 0 到 n - 2 之间的大顶堆，从堆顶 0 依次维护下去，数组 nums 就变成从小到大顺序的
        for (let i = n - 1; i >= 0; i--) {
        //这里是为了完整的堆排序，如果只是要获取第k大的
        //直接if(n==n-k-1) return nums[n-k]就行，无需再继续了
            let temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            heapify(i, 0);
        }
    }

    heap_sort();
    console.log(nums);
    return nums[n - k];
};

四、代码详细解释

1. findKthLargest 函数

这个函数是整个算法的入口，它接收两个参数：nums 数组和 k。首先，我们获取数组的长度 n，然后调用 heap_sort 函数对数组进行排序，最后返回排序后数组的第 n - k 个元素，即为第 k 个最大的元素。

2. heapify 函数

这个函数用于维护以 i 为父节点的子树的大顶堆性质。具体步骤如下：

• 初始化 lastMax 为 i，表示当前最大节点为父节点。
• 计算左子节点的索引 lson = 2 * i + 1 和右子节点的索引 rson = 2 * i + 2。
• 比较左子节点和父节点的大小，如果左子节点更大，则更新 lastMax 为左子节点的索引。
• 比较右子节点和当前最大节点的大小，如果右子节点更大，则更新 lastMax 为右子节点的索引。
• 如果 lastMax 不等于 i，说明需要交换父节点和最大子节点的位置，然后递归调用 heapify 函数，继续维护以 lastMax 为根节点的子树的大顶堆性质。

3. heap_sort 函数

这个函数是大顶堆排序的入口，具体步骤如下：

• 构建大顶堆：从最后一个非叶子节点开始，依次调用 heapify 函数，将数组转换为大顶堆。最后一个非叶子节点的索引为 Math.floor(n / 2 - 1)。
• 排序：将堆顶元素（即数组的第一个元素）与数组的最后一个元素交换，然后将堆的大小减 1，再次调用 heapify 函数维护堆的性质。重复这个过程，直到堆的大小为 1，此时数组就已经按从小到大的顺序排序好了。