堆排序（Heap Sort）的进阶应用：Top K 问题的高效解法

题目：给定一个整数数组 nums 和一个整数 k，请设计一个高效的算法，找出数组中前 k 个最大的元素。返回的结果顺序可以是任意的。

1. 问题分析
我们的目标不是对整个数组进行完整的排序（时间复杂度 O(n log n)），而是只找出最大的 k 个元素。一个直观但低效的方法是先排序再取前 k 个。我们需要一个更优的解法，其时间复杂度应优于 O(n log n)。

2. 核心思路：利用堆（Heap）数据结构
堆是一种特殊的完全二叉树，它满足：每个节点的值都大于或等于其子节点的值（大顶堆），或者每个节点的值都小于或等于其子节点的值（小顶堆）。
这个性质使得堆的根节点总是极值（最大值或最小值），我们可以利用这个特性来高效地维护一个候选集合。

对于“前 K 个最大”的问题，我们可以维护一个大小为 k 的小顶堆。

• 堆顶（根节点）是这个大小为 k 的堆中的最小值。
• 任何新来的元素，如果它比当前堆顶（即当前第 k 大的候选值）还要大，就说明它有资格进入“前 K 大”的名单。这时，我们移除当前最小的堆顶，加入这个更大的新元素，并重新调整堆，以保持堆顶仍然是新的最小值。
• 遍历完所有元素后，这个大小为 k 的小顶堆里存放的就是整个数组中最大的 k 个元素。

为什么用小顶堆？
因为我们关心的是“最大”的 k 个，我们需要一个门槛来快速判断新元素是否有资格入选。这个门槛就是当前已入选的 k 个元素里“最弱”的那个（即最小值）。小顶堆的堆顶正好就是这个“最弱”的门槛。

3. 逐步推演
假设数组为 nums = [3, 2, 1, 5, 6, 4], k = 3。我们目标是找出前 3 大的元素 [6, 5, 4]（顺序不限）。

步骤 1: 初始化堆

• 我们先将前 k 个元素 [3, 2, 1] 构建成一个小顶堆。
• 构建后，堆结构如下（数字表示值，堆顶是最小值）：

      1
     / \
    3   2

• 此时堆顶是 1。这个堆代表当前找到的“最大的3个元素”的候选，但显然 [1, 2, 3] 并不是最终结果。

步骤 2: 处理剩余元素

• 下一个元素是 5。比较 5 和堆顶 1。
• 5 > 1，所以 5 有资格入选。我们移除当前堆顶 1，将 5 加入并调整堆。
• 调整后的堆为（将 5 放在根节点，然后与较小的子节点交换，以维持小顶堆性质）：

      2
     / \
    3   5

• 新的堆顶是 2。

步骤 3: 继续处理

• 下一个元素是 6。比较 6 和堆顶 2。
• 6 > 2，所以 6 有资格入选。移除堆顶 2，加入 6 并调整堆。
• 调整后的堆为：

      3
     / \
    6   5

• 新的堆顶是 3。

步骤 4: 处理最后一个元素

• 下一个元素是 4。比较 4 和堆顶 3。
• 4 > 3，所以 4 有资格入选。移除堆顶 3，加入 4 并调整堆。
• 调整后的堆为：

      4
     / \
    6   5

• 新的堆顶是 4。

步骤 5: 得到结果

• 所有元素处理完毕。最终堆中包含的元素是 [4, 5, 6]（内部结构如上，但顺序无关紧要）。
• 这三个数就是原数组中最大的 k=3 个元素。

4. 复杂度分析

• 时间复杂度：O(n log k)
  • 建一个大小为 k 的堆：O(k)。
  • 我们遍历了剩下的 n - k 个元素。对于每个元素，最坏情况下需要进行一次堆调整（插入或删除堆顶），每次堆调整的时间复杂度是 O(log k)。
  • 因此总时间复杂度是 O(k + (n - k) log k) ≈ O(n log k)。当 k 远小于 n 时，这比 O(n log n) 的全排序要高效得多。
• 空间复杂度：O(k) 或 O(1)
  • 如果我们使用额外的堆数据结构，空间复杂度是 O(k)。
  • 如果可以修改原数组，我们可以使用原数组的前 k 个位置来模拟堆，这样空间复杂度可以降到 O(1)。

5. 关键要点总结

• 对于“前 K 大”问题，使用小顶堆来维护一个大小为 k 的候选集。
• 堆顶是候选集中的最小值，作为判断新元素能否入选的门槛。
• 算法效率 O(n log k) 在处理大规模数据且 k 较小优势明显。
• 相反，如果是找“前 K 小”的问题，则应使用大顶堆，堆顶是候选集中的最大值。