排序算法之：利用最小堆实现“数组中的第K个最大元素”的快速选择变体

题目描述

给定一个整数数组 nums 和一个整数 k，要求在不完全排序整个数组的情况下，找出数组中第 k 个最大的元素。请注意，第 k 个最大元素指的是排序后从大到小第 k 个元素（即升序排序后索引为 n - k 的元素）。
例如：
nums = [3,2,1,5,6,4], k = 2 → 排序后为 [1,2,3,4,5,6]，第 2 个最大的元素是 5。
要求时间复杂度尽可能低，并且不需要修改原数组（若需修改，可说明）。

解题思路

最直接的解法是将数组完全排序后取第 n - k 个元素，时间复杂度为 O(n log n)。但我们可以利用快速选择算法（QuickSelect） 或堆（Heap） 来优化。
本题重点讲解最小堆（Min Heap） 的解法：

• 维护一个大小为 k 的最小堆，堆顶是当前堆中最小的元素。
• 遍历数组，当堆大小小于 k 时直接插入；当堆大小等于 k 时，如果当前元素大于堆顶，则替换堆顶并调整堆。
• 遍历完成后，堆顶就是第 k 个最大的元素。

为什么用最小堆？
因为最小堆的堆顶是堆中最小的元素，而我们要找的是第 k 个最大的元素。如果堆中保留的是当前看到的最大的 k 个元素，那么这 k 个元素中最小的那个（即堆顶）就是第 k 个最大的元素。

逐步讲解

步骤 1：理解堆的性质

• 最小堆：每个节点的值都小于或等于其子节点的值，根节点是堆中的最小值。
• 堆可以用数组实现，若节点索引为 i，则：
  • 左子节点索引：2 * i + 1
  • 右子节点索引：2 * i + 2
  • 父节点索引：(i - 1) // 2

步骤 2：算法流程

1. 初始化一个空的最小堆（可以用数组模拟，或直接使用语言提供的优先队列）。
2. 遍历数组 nums 的每个元素 num：
   • 如果堆的大小 < k，将 num 插入堆中。
   • 否则（堆大小 == k），比较 num 与堆顶：
     • 如果 num > 堆顶，说明当前堆顶不是前 k 大元素之一（因为出现了更大的 num），于是弹出堆顶，插入 num。
     • 如果 num ≤ 堆顶，忽略（因为它不会进入前 k 大）。
3. 遍历完成后，堆顶即为第 k 个最大的元素。

步骤 3：具体例子演示

以 nums = [3,2,1,5,6,4], k = 2 为例：

• 初始化堆 heap = []。
• 遍历：
  • num = 3，堆大小 0 < 2，插入 → heap = [3]（调整后仍为 [3]）。
  • num = 2，堆大小 1 < 2，插入 → heap = [2,3]（调整后：根为 2，子为 3）。
  • num = 1，堆大小 2 == 2，1 ≤ 堆顶(2)，忽略。
  • num = 5，堆大小 2 == 2，5 > 堆顶(2)，弹出堆顶 2，插入 5 → heap = [3,5]（调整后：根为 3，子为 5）。
  • num = 6，堆大小 2 == 2，6 > 堆顶(3)，弹出堆顶 3，插入 6 → heap = [5,6]（根为 5，子为 6）。
  • num = 4，堆大小 2 == 2，4 ≤ 堆顶(5)，忽略。
• 结束，堆顶为 5，即第 2 个最大的元素。

步骤 4：复杂度分析

• 时间复杂度：O(n log k)。
  每次堆插入或删除的调整时间为 O(log k)，共进行 n 次操作。
• 空间复杂度：O(k)。
  堆中最多保存 k 个元素。

步骤 5：边界情况

• 如果 k > n 或 k ≤ 0，问题无解（但题目通常保证 1 ≤ k ≤ n）。
• 数组可能包含重复元素，算法依然适用（例如 [3,3,2,1], k=2 → 第 2 个最大的元素是 3）。
• 若 k = n，则堆会保留所有元素，堆顶是全局最小值，即第 n 个最大的元素（最小的元素）。

代码实现（Python）

import heapq

def findKthLargest(nums, k):
    min_heap = []
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        else:
            if num > min_heap[0]:
                heapq.heapreplace(min_heap, num)  # 弹出堆顶并插入新元素
    return min_heap[0]  # 堆顶即为第k个最大元素

关键点解释：

• heapq.heapreplace(heap, item) 相当于先 heappop 再 heappush，但效率更高。
• 如果使用最大堆，可以插入 -num，但需要额外处理符号。

对比快速选择算法

• 快速选择 基于快速排序的分区思想，平均时间复杂度 O(n)，最坏 O(n²)，但可以通过中位数优化避免最坏情况。
• 最小堆 时间复杂度稳定为 O(n log k)，适合 k 远小于 n 的场景（如找前 10 个最大元素），且代码简洁，不易出错。

总结

利用最小堆求第 k 个最大元素，核心是维护一个大小为 k 的最小堆，保存当前最大的 k 个元素。这种方法既避免了完全排序，又保证了效率，是处理 Top K 问题的经典思路。