教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/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左右子节点下标为2i1与2i2。下图即为仓库 堆.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。常用 APIadd(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) { PriorityQueueInteger 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/下沉。文档还给出一个典型的大根堆优先队列骨架MaxPQKey extends ComparableKey用数组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算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/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堆章节中的教程文档示例工程教育上一篇大语言模型平民化实践TinyLLM在有限资源下的高效构建方案下一篇408考频表怎么用一条130个知识点的复习路径创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
