企业官网建设流程全解析

Hello 算法中的 Top-k 问题：从 O(nk) 遍历到 O(n log k) 堆解法全解析

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

给定一个长度为 $n$ 的无序数组nums，返回其中最大的 $k$ 个元素——这就是经典的 Top-k 问题。本文以《Hello 算法》（hello-algo）堆章节 中的 Top-k 专题文档 为骨架，完整梳理遍历选择、排序、堆三种解法的思路与复杂度，并结合仓库中 Python、Java、C++、C、Go 等多语言实现，深入剖析"小顶堆维护 Top-k"这一高效方案的原理、边界与动态数据流扩展。读完本文，你将掌握 Top-k 问题的完整解法谱系，并能直接运行仓库代码验证结论。

问题定义

!!! question

给定一个长度为 $n$ 的无序数组 `nums`，请返回数组中最大的 $k$ 个元素。

例如对数组nums = [1, 7, 6, 3, 2]且 $k = 3$，应返回{6, 7, 3}（顺序无关）。这个问题看似简单，但不同解法的时间复杂度差异巨大：从 $O(nk)$ 到 $O(n \log n)$，再到 $O(n \log k)$。下面按效率从低到高逐一展开。

方法一：遍历选择（k 轮扫描）

最直接的思路是进行 $k$ 轮遍历：每一轮遍历整个数组，提取当前剩余元素中的最大值，第 $1$、$2$、$\dots$、$k$ 轮依次得到第 $1$ 大、第 $2$ 大……第 $k$ 大的元素。

• 时间复杂度：$O(nk)$，因为每轮遍历需要 $O(n)$，共 $k$ 轮。
• 适用场景：仅适合 $k \ll n$ 的情况。当 $k$ 与 $n$ 接近时，复杂度趋向 $O(n^2)$，非常耗时。
• 边界提示：当 $k = n$ 时，整个过程会得到完整的有序序列，此时等价于"选择排序"算法——这正好呼应了仓库中 选择排序的实现 的每轮选取极值的思路。

方法二：全量排序

更"省事"的做法是直接排序：对nums整体排序后，取最右侧的 $k$ 个元素（升序排列时即最大的 $k$ 个）。

• 时间复杂度：$O(n \log n)$，由排序算法主导。
• 核心缺陷：该方法"超额"完成了任务——我们只需要最大的 $k$ 个元素，却把其余 $n - k$ 个元素的相对顺序也全部排好了，这部分计算完全是浪费。

方法三：基于小顶堆的高效解法

Top-k 问题可以用堆更高效地解决。核心思路是：维护一个容量为 $k$ 的小顶堆，堆中始终保存当前已扫描元素中最大的 $k$ 个。具体流程如下：

1. 初始化一个小顶堆，其堆顶元素是堆中最小的元素；
2. 先将数组的前 $k$ 个元素依次入堆（此时堆容量恰为 $k$）；
3. 从第 $k+1$ 个元素开始逐个扫描：若当前元素大于堆顶元素，则弹出堆顶，将当前元素入堆（堆始终只保留最大的 $k$ 个）；
4. 遍历完成后，堆中保存的就是数组中最大的 $k$ 个元素。

该策略的精妙之处在于：堆顶是小顶堆中最小的元素，即当前 Top-k 的"门槛"。任何小于等于堆顶的元素都不可能进入 Top-k，可以直接跳过；任何大于堆顶的元素则替换掉门槛，同时 $O(\log k)$ 的堆化操作让堆重新恢复有序结构。完整 9 步动画示意图见 top_k.assets 目录 下的top_k_heap_step1.png至top_k_heap_step9.png。

复杂度分析

• 总共执行 $n$ 轮入堆/出堆操作（前 $k$ 个元素只入不出，后 $n-k$ 个元素至多触发一次替换）；
• 堆的最大长度为 $k$，每次入堆、出堆的堆化开销均为 $O(\log k)$；
• 总时间复杂度为 $O(n \log k)$，空间复杂度为 $O(k)$（仅堆本身）。

该方法的效率曲线非常优秀：当 $k$ 较小时，$O(n \log k)$ 趋向 $O(n)$；当 $k$ 较大时，时间复杂度也不会超过 $O(n \log n)$——即不会比全量排序更差。

动态数据流场景

堆解法天然适配动态数据流：当新数据不断到达时，无需重新扫描或排序全部历史数据，只需对新元素执行一次"与堆顶比较、必要时替换"的操作，即可持续维护当前最大的 $k$ 个元素。这使其成为流式统计、实时排行榜、大规模日志 Top-k 监控等场景的首选结构。

仓库源码级实现解析

《Hello 算法》在 chapter_heap 目录下提供了 Top-k 的多语言实现，核心函数统一命名为top_k_heap。下面从几种代表性语言看实现细节。

Python：借助标准库 heapq

Python 实现 直接使用标准库heapq构建小顶堆，逻辑最直白：

def top_k_heap(nums: list[int], k: int) -> list[int]: """基于堆查找数组中最大的 k 个元素""" # 初始化小顶堆 heap = [] # 将数组的前 k 个元素入堆 for i in range(k): heapq.heappush(heap, nums[i]) # 从第 k+1 个元素开始，保持堆的长度为 k for i in range(k, len(nums)): # 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆 if nums[i] > heap[0]: heapq.heappop(heap) heapq.heappush(heap, nums[i]) return heap

注意heap[0]即堆顶（最小值），nums[i] > heap[0]的判断与算法第 3 步完全对应。驱动代码使用nums = [1, 7, 6, 3, 2]、k = 3验证，并通过 modules 中的 print_heap 以树形打印堆结果。

Java：PriorityQueue 小顶堆

Java 实现 用PriorityQueue<Integer>作为堆，默认即小顶堆，配合offer/poll/peek三个 API 完成入堆、出堆、看堆顶：

Queue<Integer> heap = new PriorityQueue<Integer>(); for (int i = 0; i < k; i++) { heap.offer(nums[i]); } for (int i = k; i < nums.length; i++) { if (nums[i] > heap.peek()) { heap.poll(); heap.offer(nums[i]); } }

C++：greater 比较器的优先队列

C++ 实现 的关键在于priority_queue<int, vector<int>, greater<int>>——默认的priority_queue是大顶堆，通过传入greater<int>比较器翻转成小顶堆：

priority_queue<int, vector<int>, greater<int>> topKHeap(vector<int> &nums, int k) { priority_queue<int, vector<int>, greater<int>> heap; for (int i = 0; i < k; i++) { heap.push(nums[i]); } for (int i = k; i < nums.size(); i++) { if (nums[i] > heap.top()) { heap.pop(); heap.push(nums[i]); } } return heap; }

Go：container/heap 接口实现

Go 实现 需要自定义类型实现container/heap的Len/Less/Swap/Push/Pop接口，其中Less定义为<即构成小顶堆，并额外提供Top方法读取堆顶：

func topKHeap(nums []int, k int) *minHeap { h := &minHeap{} heap.Init(h) for i := 0; i < k; i++ { heap.Push(h, nums[i]) } for i := k; i < len(nums); i++ { if nums[i] > h.Top().(int) { heap.Pop(h) heap.Push(h, nums[i]) } } return h }

C：取反技巧——用大顶堆模拟小顶堆

C 语言实现 最具工程技巧性：由于仓库的 my_heap.c 只实现了大顶堆MaxHeap，Top-k 解法通过元素取反的技巧复用大顶堆——入堆存-val、出堆返回-pop(...)，从而用大顶堆模拟出小顶堆的语义。这也解释了为什么topKHeap中比较用nums[i] > peekMinHeap(maxHeap)（此时堆顶存的是负数，取反后才是真实最小值）。该文件直接#include "my_heap.c"复用堆的push/pop/peek与数组扩容逻辑，并显式malloc/free管理结果内存。

三种方法对比与选型建议

选型建议：只要目标是"找出最大的 $k$ 个"而非"全部排序"，堆解法几乎总是更优；当数据持续到达、无法一次性加载时，堆解法更是唯一可行方案。文中核心结论均可在仓库 Top-k 文档、堆章节文档 及各语言实现（如 Python、Java、C++、C、Go）中逐一验证，读者可直接运行各语言驱动代码观察输出结果。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo