- 教程
【免费下载链接】Learn-Algorithms
算法学习笔记
Top-K 问题（从 n 个数中找出最大的 k 个数，或最小的 k 个数）是算法面试与海量数据处理的经典高频考点，也是 Learn-Algorithms 仓库中“堆”这一数据结构章节的核心应用场景。本文将以仓库文档 Top-K 问题 为骨架，结合 堆（大顶堆与小顶堆）、数列查找章节、海量数据处理 与 C 语言堆实现骨架，完整梳理排序、部分排序、堆三种求解思路，并给出可复制的 Java 代码与复杂度分析，帮助读者理解“Top-K 大用小根堆、Top-K 小用大根堆”这一核心结论的来龙去脉。
问题定义与复杂度直觉
问题描述：从arr[1, n]这 n 个数中，找出最大的 k 个数，这就是经典的 Top-K 问题。例如输入1, 2, 3, 4, 5, 6, 7, 8这 8 个数字，最大的 4 个数字为5, 6, 7, 8；最小的 4 个数字为1, 2, 3, 4（仓库 5.4 数列-查找 给出了该变体）。
求解 Top-K 主要有三条思路，仓库 Top-K 问题 将其总结为：
- 全局排序：对整个数组排序后取前 k 个，最直观但复杂度高；
- 冒泡式部分排序：只对最大的 k 个数排序，例如对 k 个最大的数执行 k 轮冒泡；
- 堆：只找最大的 k 个数，这 k 个数本身不需要有序，用小根堆维护当前最大的 k 个元素。
三种思路的核心差异在于：是否需要让所有元素“有序”。全局排序做了大量无用功——我们只关心前 k 个，却把 n-k 个元素的相对次序也排好了。堆方案正是针对这一浪费做的优化。
方案一：全局排序
最简单直接的做法是先把 n 个数整体排序，再取出前 k 个。仓库 6 Sort/README.md 指出，常见的比较排序算法时间复杂度通常为 O(n²) 或 O(n log n)。因此全局排序方案的时间复杂度为：
- 快排、归并、堆排序等：O(n log n)
- 冒泡、插入、选择排序：O(n²)
当 n 很大时，排序的代价被放大，而且如果数据量超过内存容量（例如 2 亿个整数），连“一次性全部装入内存”都做不到，全局排序还会带来巨大的磁盘 IO 开销（参见 海量数据处理 对“空间上无法一次全部装入内存”的论述）。所以全局排序只适合 n 较小、对 k 没有特殊要求的场景。
方案二：冒泡式部分排序
改进思路是“只排我需要的”。以冒泡排序为例，冒泡每轮会将当前未排序部分的最大值“冒”到末尾，因此执行 k 轮冒泡，即可确定最大的 k 个数，复杂度为 O(n·k)。
仓库 5.4 数列-查找 给出了一个用冒泡找第 k 大数的 Java 实现：
// 冒泡实现：执行 k 轮冒泡后，nums[nums.length - k] 即为第 k 大的数 public int findK(int[] nums, int k){ // base case if (nums == null || nums.length < k) { return -1; } for (int i = 1; i <= k; i++){ for (int j = 0; j < nums.length - i; j++) { int next = j + 1; if (nums[j] > nums[next]) { int tmp = nums[j]; nums[j] = nums[next]; nums[next] = tmp; } } } return nums[nums.length - k]; }部分排序比全局排序省掉了一部分计算，但当 k 接近 n 时，O(n·k) 退化为 O(n²)。文档进一步指出：当 k 较大时（比如“2 亿个整数中求最大的 100 万之和”这类题目），维护一个大小为 k 的数组做插入排序，每轮还有“寻找插入位置 + 移动数组元素”的 CPU 消耗，复杂度是 O(n·k)。有没有一种数据结构既能快速查找最小值/最大值，又能以 O(1) 复杂度完成替换后的堆顶访问？答案就是二叉堆。
方案三：堆——Top-K 的经典解法
堆的基本性质
先回顾堆结构（详见 堆（大顶堆与小顶堆））：
- 堆也被称为优先队列、二叉堆；
- 堆总是一棵完全二叉树，使用数组作为存储结构；
- 任一节点小于（或大于）其所有孩子节点；
- 若根节点大于所有孩子节点，则为大根堆（根是堆上的最大值）；若根节点小于所有子节点，则为小根堆（根是堆上的最小值）。
因为堆是完全二叉树且用数组存储，节点下标之间有确定关系（文档中用的是从 0 开始的下标约定）：节点 i 的父节点下标为(i-1)/2，左右子节点下标为2i+1与2i+2。下图即为仓库 堆.md 给出的小根堆数组存储示例（图片位于 4 Tree/8-堆/pq-1.jpg）：
为什么 Top-K 大用小根堆
这是全文最关键的结论，仓库在 Top-K 问题 与 5.4 数列-查找 中反复强调：
top-k 小的时候用大根堆，top-k 大的时候用小根堆。
推导逻辑如下（以求最大的 k 个数为例）：
- 先取前 k 个元素，构建一个大小为 k 的小根堆，堆顶（根）是这 k 个元素中最小的那个；
- 遍历剩下的 n-k 个元素：每个元素与堆顶比较，堆顶元素小于当前元素时，用当前元素替换堆顶并调整堆，保证堆内始终是“当前已见过的最大 k 个元素”；
- 扫描结束后，堆中的 k 个元素就是全局最大的 k 个数（这 k 个数之间无需有序），堆顶即第 k 大的数。
为什么不能用大根堆？因为大根堆的堆顶是当前 k 个元素中的最大值，用它去比较无法判断新元素是否应该进入“前 k 名”——你只能淘汰堆内最小的元素，而最小值只有小根堆能在 O(1) 时间给出。
复杂度分析（仓库 5.4 数列-查找 有明确表述）：遍历每个元素与堆顶比较是 O(1)，替换后调整堆是 O(log k)，因此整体复杂度为O(n·log k)，且空间复杂度仅 O(k)，远优于 O(n·k) 的部分排序和 O(n log n) 的全局排序。
Java 实现：PriorityQueue 小根堆
仓库 堆.md 指出，Java 的PriorityQueue类就是通过二叉小顶堆实现的优先级队列，具有如下特点：
- 实现
Queue接口； - 头部是基于自然排序或基于比较器排序的最小元素；
- 不是线程安全的，并发环境中应使用
PriorityBlockingQueue。
常用 API：add(object)插入元素、offer(object)插入元素、remove(object)删除指定元素、poll()检索并删除头部（空队列返回 null）、element()检索不删除头部（空队列抛异常）、peek()检索不删除头部（空队列返回 null）、clear()清空队列。
利用PriorityQueue实现 Top-K 大问题的代码如下（出自 堆.md 与 5.4 数列-查找，两处一致）：
/** * 小根堆实现：求 nums 中第 k 大的数（即最大的 k 个数中最小的那个） */ public static int findMaxK(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> (a - b)); for (int i = 0; i < nums.length; i++) { // 取出前 k 个元素放入 PQ 中 if (i < k) { pq.add(nums[i]); continue; } Integer head = pq.peek(); if (head < nums[i]) { // 维护 priorityQueue 中元素只有 k 个 pq.poll(); pq.add(nums[i]); } } return pq.poll(); }其中(a, b) -> (a - b)是升序比较器，使PriorityQueue表现为小根堆，peek()得到的是堆内最小元素（即当前“前 k 名”的门槛）。代码骨架可进一步扩展为 Top-K 小：改用大根堆（比较器改为(b - a)），遍历时若堆顶大于当前元素则替换堆顶，最终堆内即为最小的 k 个数。
堆的存储结构与调整操作
堆之所以能高效支持“替换堆顶 + 重新调整”，是因为它的三个基本操作（仓库 堆.md 归纳）：
- 建堆：将无序数组堆化为合法堆；
- 插入：插入到数组末尾，再向上调整（swim/上浮）满足堆次序；
- 删除：删除总是发生在根节点 A[0] 处，通常把最后一个元素提到根位置，再向下调整（sink/下沉）。
文档还给出一个典型的大根堆优先队列骨架MaxPQ<Key extends Comparable<Key>>：用数组pq存储元素（索引 0 不用），维护当前元素个数N，对外提供max()、insert(e)、delMax()，对内实现swim(k)上浮、sink(k)下沉、exch(i, j)交换与less(i, j)比较。这正是堆排序与 Top-K 的核心“引擎”。
仓库还提供了对应的 C 语言接口骨架 heap.c，包含heap_build(int *a, int length)（建堆）、heap_insert(int *a, int v)（插入）、heap_delete(int *a, int *value)（删除，删除的元素放入 value 指向的内存），供读者对照实现 C 版 Top-K：
// 插入 void heap_insert(int *a, int v); // 删除，删除的元素放在 value 指向的内存中 void heap_delete(int *a, int *value);插入或删除元素后，必须重新调整以满足堆次序；调整时从左右孩子中找合适的节点交换，若父节点已经满足堆性质则无需继续。堆排序正是反复利用这一性质：建立大根堆后，交换根与末尾元素，再对剩余部分向下调整，即可完成递增排序（详见 6 Sort/README.md 的堆排序小节与 堆.md）。
延伸：Top-K 在海量数据处理中的应用
当数据规模大到无法装入内存（如 1G 文件、2 亿个整数、1 亿个随机整数）时，Top-K 的堆解法几乎是标配，仓库 海量数据处理 给出了大量实战题目与方案：
- 100w 个数中找出最大的 100 个数；
- 300 万个查询字符串中统计最热门的 10 个查询；
- 2 亿个整数中求最大的 100 万个整数之和；
- 一千万条短信中找出重复出现最多的前 10 条；
- 1 亿个随机整数中快速找到最大（小）的 100 万个数字（时间复杂度 O(n log k)）；
- 1G 文件、每行一个词（不超过 16 字节）、内存限制 1M，返回频数最高的 100 个词。
这些题目的通用解法归纳为“hash 统计 + 堆”：先用 hash 统计频率或去重，再用一个固定大小 k 的堆（Top-K 大用最小堆、Top-K 小用最大堆）在流式扫描中维护前 k 名，复杂度 O(n log k)。文档中给出的方案还包括：
- 方案 1（堆）：用含 k 个元素的最小堆，复杂度 O(n log k)，例如
O(100w * lg100)； - 方案 2（快排思想）：每次分割后只考虑比轴大的一部分，直到剩余部分略多于 100 时改用传统排序取前 100，复杂度 O(n·k)；
- 方案 3（局部淘汰 + 插入排序）：先取前 k 个排序记为序列 L，扫描剩余元素，若大于 L 中最小元素则删除最小者并插入 L，复杂度 O(n·k)。
三者在常数因子与实现难度上各有取舍，但堆方案在内存占用（O(k)）与最坏情况稳定性上通常更优。这也是为什么堆（配合分治、Hash 映射、外排序）被列入海量数据处理的常用武器库（见 海量数据处理 的总结：Hash 映射/分而治之 + hash 统计/trie 树/红黑树/二叉搜索树 + 堆排序/快速排序/归并排序）。
小结：三种方案的选择
| 方案 | 核心思想 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 全局排序 | 整体排序后取前 k 个 | O(n log n) 或 O(n²) | O(n) | n 较小、一次性可装入内存 |
| 冒泡式部分排序 | 只对前 k 个排序 | O(n·k) | O(1) | k 较小、实现简单 |
| 堆 | 固定大小 k 的堆维护前 k 名 | O(n log k) | O(k) | n 巨大（含海量数据流式场景） |
记住口诀：Top-K 大 → 小根堆（堆顶是门槛最小值），Top-K 小 → 大根堆（堆顶是门槛最大值）。堆解法用 O(k) 的空间把复杂度从 O(n log n) 降到了 O(n log k)，这也是它在面试与海量数据处理中被反复考察的根本原因。读者可继续深入阅读 堆.md、6 Sort/README.md 中的堆排序章节，以及 5.4 数列-查找 中“查找最小的 k 个元素”和“找第 k 大的数”的完整变体，进一步巩固这一主题。
- 教程
【免费下载链接】Learn-Algorithms
算法学习笔记
相关推荐
深度解析：如何掌握SMU Debug Tool释放AMD Ryzen处理器的隐藏性能
深度解析：如何掌握SMU Debug Tool释放AMD Ryzen处理器的隐藏性能 想要完全掌控AMD Ryzen处理器的性能潜力吗？SMU Debug To
教程文档示例工程教育用堆解决 Top-k 问题：从 O(nk) 到 O(n log k) 的三级进阶（Hello 算法）
用堆解决 Top k 问题：从 O nk 到 O n log k 的三级进阶（Hello 算法） 本篇技术指南以《Hello 算法》第 5 章「堆」（日文版章节
教程文档示例工程教育Hello 算法 Top-k 问题详解：遍历选择、排序与小顶堆三种解法的复杂度对比及多语言实现
Hello 算法 Top k 问题详解：遍历选择、排序与小顶堆三种解法的复杂度对比及多语言实现 本文基于《Hello 算法》（hello algo）堆章节中的
教程文档示例工程教育
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
