 遍历到 O(n log k) 堆解法全解析)
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$ 个。具体流程如下初始化一个小顶堆其堆顶元素是堆中最小的元素先将数组的前 $k$ 个元素依次入堆此时堆容量恰为 $k$从第 $k1$ 个元素开始逐个扫描若当前元素大于堆顶元素则弹出堆顶将当前元素入堆堆始终只保留最大的 $k$ 个遍历完成后堆中保存的就是数组中最大的 $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借助标准库 heapqPython 实现 直接使用标准库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]) # 从第 k1 个元素开始保持堆的长度为 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 以树形打印堆结果。JavaPriorityQueue 小顶堆Java 实现 用PriorityQueueInteger作为堆默认即小顶堆配合offer/poll/peek三个 API 完成入堆、出堆、看堆顶QueueInteger heap new PriorityQueueInteger(); 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]); } }Cgreater 比较器的优先队列C 实现 的关键在于priority_queueint, vectorint, greaterint——默认的priority_queue是大顶堆通过传入greaterint比较器翻转成小顶堆priority_queueint, vectorint, greaterint topKHeap(vectorint nums, int k) { priority_queueint, vectorint, greaterint 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; }Gocontainer/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 只实现了大顶堆MaxHeapTop-k 解法通过元素取反的技巧复用大顶堆——入堆存-val、出堆返回-pop(...)从而用大顶堆模拟出小顶堆的语义。这也解释了为什么topKHeap中比较用nums[i] peekMinHeap(maxHeap)此时堆顶存的是负数取反后才是真实最小值。该文件直接#include my_heap.c复用堆的push/pop/peek与数组扩容逻辑并显式malloc/free管理结果内存。三种方法对比与选型建议方法时间复杂度空间复杂度适用场景遍历选择$O(nk)$$O(1)$仅 $k \ll n$ 且实现最简单全量排序$O(n \log n)$视排序算法而定需要完整有序序列时小顶堆 Top-k$O(n \log k)$$O(k)$通用场景尤其适合 $k$ 较小或动态数据流选型建议只要目标是找出最大的 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法中的 Top-k 问题：从 O(nk) 遍历到 O(n log k) 堆解法全解析
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$ 个。具体流程如下初始化一个小顶堆其堆顶元素是堆中最小的元素先将数组的前 $k$ 个元素依次入堆此时堆容量恰为 $k$从第 $k1$ 个元素开始逐个扫描若当前元素大于堆顶元素则弹出堆顶将当前元素入堆堆始终只保留最大的 $k$ 个遍历完成后堆中保存的就是数组中最大的 $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借助标准库 heapqPython 实现 直接使用标准库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]) # 从第 k1 个元素开始保持堆的长度为 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 以树形打印堆结果。JavaPriorityQueue 小顶堆Java 实现 用PriorityQueueInteger作为堆默认即小顶堆配合offer/poll/peek三个 API 完成入堆、出堆、看堆顶QueueInteger heap new PriorityQueueInteger(); 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]); } }Cgreater 比较器的优先队列C 实现 的关键在于priority_queueint, vectorint, greaterint——默认的priority_queue是大顶堆通过传入greaterint比较器翻转成小顶堆priority_queueint, vectorint, greaterint topKHeap(vectorint nums, int k) { priority_queueint, vectorint, greaterint 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; }Gocontainer/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 只实现了大顶堆MaxHeapTop-k 解法通过元素取反的技巧复用大顶堆——入堆存-val、出堆返回-pop(...)从而用大顶堆模拟出小顶堆的语义。这也解释了为什么topKHeap中比较用nums[i] peekMinHeap(maxHeap)此时堆顶存的是负数取反后才是真实最小值。该文件直接#include my_heap.c复用堆的push/pop/peek与数组扩容逻辑并显式malloc/free管理结果内存。三种方法对比与选型建议方法时间复杂度空间复杂度适用场景遍历选择$O(nk)$$O(1)$仅 $k \ll n$ 且实现最简单全量排序$O(n \log n)$视排序算法而定需要完整有序序列时小顶堆 Top-k$O(n \log k)$$O(k)$通用场景尤其适合 $k$ 较小或动态数据流选型建议只要目标是找出最大的 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考