第 14 关 | 刷题模板之堆结构：2. 白银挑战——堆能高效解决的经典问题-灵析社区

1. 数组中找第 K 大的元素

LeetCode215 给定整数数组nums和整数k，请返回数组中第k个最大的元素。 请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

示例1：
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例2：
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

这个题是一道非常重要的题，主要解决方法有三个，选择法，堆查找法和快速排序法。

选择法很简单，就是先遍历一遍找到最大的元素，然后再遍历一遍找第二大的，然后再遍历一遍找第三大的，直到第K次就找到了目标值了。但是这种方法只适合在面试的时候预热，面试官不会让你这么简单就开始写代码，因为该方法的时间复杂度为O(NK)。

比较好的方法是堆排序法和快速排序法。快速排序我们已经分析过，这里先看堆排序如何解决问题。

这个题其实用大堆小堆都可以解决的，但是我们推荐“找最大用小堆，找最小用大堆，找中间用两个堆”，这样更容易理解，适用范围也更广。我们构造一个大小只有4的小根堆，为了更好说明情况，我们扩展一下序列[3,2,3,1, 2 ,4 ,5, 1,5,6,2,3]。

堆满了之后，对于小根堆，并一定所有新来的元素都可以入堆的，只有大于根元素的才可以插入到堆中，否则就直接抛弃。这是一个很重要的前提。

另外元素进入的时候，先替换根元素，如果发现左右两个子树都小该怎么办呢？很显然应该与更小的那个比较，这样才能保证根元素一定是当前堆最小的。假如两个子孩子的值一样呢？那就随便选一个。

新元素插入的时候只是替换根元素，然后重新构造成小堆，完成之后，你会神奇的发现此时根的根元素正好是第4大的元素。

这时候你会发现，不管要处理的序列有多大，或者是不是固定的，根元素每次都恰好是当前序列下的第K大元素。上面的图收篇幅所限，我们省略了部分调整环节，请读者自行画一下看看。

上的代码自己实现是非常困难的，我们可以使用jdk的优先队列来解决，其思路是很简单的。由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：

●如果当前堆不满，直接添加；

●堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新遍历到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

说明：这里最合适的操作其实是 replace()，即直接把新读进来的元素放在堆顶，然后执行下沉（siftDown()）操作。Java 当中的 PriorityQueue 没有提供这个操作，只好先 poll() 再 offer()。

优先队列的写法就很多了，这里只例举一个有代表性的，其它的写法大同小异，没有本质差别。

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(k>nums.length){
            return -1;
        }
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            // 看一眼，不拿出，因为有可能没有必要替换
            Integer topEle = minHeap.peek();
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topEle) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }
}

在C++里没有找到现成的二叉堆，要自己实现部分功能

void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};