准备高级后端面试时，面试官抛来一道经典题：“给定一个包含 n 个整数的无序数组，返回其中最大的 k 个元素。” 我第一反应是排序后切片：先把整个数组排好序，再取前 k 个。O(n log n) 听起来也没什么问题……但面试官显然在等更优的答案。我反复想：“既然只需要 top k，真的有必要把整个数组都排一遍吗？”那种感觉就像面对一扇锁着的门，手里攥着一串不匹配的钥匙，明知道正确的钥匙就在附近，却一时找不到。 这个瞬间让我真正开始理解堆和优先队列。之前听说过这些名词，但没意识到它们到底特殊在哪。后来才发现，堆的神奇之处不只是能快速拿到最小/最大值，而是：把一个无序数组建成堆，只需要线性时间。这个洞察改变了我对很多问题的看法。 堆本质上是一棵存储在数组中的二叉树，每个父节点与子节点之间满足固定顺序：最小堆中父节点 ≤ 子节点，最大堆中父节点 ≥ 子节点。 更妙的是，对任意无序数组执行“堆化”，从最后一个内部节点开始，逐层向下调整，就能在 O(n) 时间内得到一个合法堆，而不是 O(n log n)。 为什么堆化是 O(n) 而不是 O(n log n)？ 先看常规思路：往堆里插入 n 个元素，每次插入 O(log n)，所以总复杂度是 O(n log n)。 但自底向上堆化不一样：高度越低、节点越多，而每个节点向下调整的代价越小。 - 最底层有 n/2 个叶子节点，不需要下沉； - 上一层有 n/4 个节点，最多下沉 1 次； - 再上一层有 n/8 个节点，最多下沉 2 次； - 依此类推。 总工作量约为： n/4 × 1 + n/8 × 2 + n/16 × 3 + ... = O(n) 这就是“数组建堆可以线性完成”的直觉来源，也是它最反直觉的地方。 有了合法堆之后，每次取出最小/最大值只需要 O(log n)，因为只需要修复从根到叶子的一条路径。对“k 个最大元素”问题，可以维护一个大小为 k 的最小堆： 1. 先把前 k 个数建成堆，O(k)； 2. 遍历剩余 n-k 个数，如果当前元素比堆顶大，就替换堆顶并调整堆； 3. 遍历结束后，堆中的 k 个元素就是数组中最大的 k 个元素，其中堆顶是它们中最小的那个。 整体时间复杂度 O(n log k)。当 n 很大、k 很小时，这比 O(n log n) 的全排序高效得多。 先看最直接的排序解法： ```python def k_largest_sort(nums, k): # O(n log n) 时间，O(n) 空间（CPython 的 Timsort 需要额外空间） return sorted(nums, reverse=True)[:k] ``` 简单，但当 n 巨大、k 很小时非常浪费。 用最小堆实现： ```python import heapq def k_largest_heap(nums, k): """ 返回数组中最大的 k 个元素。 使用大小为 k 的最小堆。 时间：O(k) 建堆 + O((n-k) log k) ≈ O(n log k) 空间：O(k) """ if k <= 0: return [] heap = nums[:k] heapq.heapify(heap) # 建堆是 O(k) for x in nums[k:]: if x > heap[0]: heapq.heapreplace(heap, x) return sorted(heap, reverse=True) ``` 代码里用 `heapreplace` 而不是先 `pop` 再 `push`，它更高效，时间复杂度仍然是 O(log k)。 当时我突然意识到，从无序列表线性建堆的方法，像在废品堆里找到了一把真正匹配的钥匙。之前所有模糊的“一定还有更好的办法”，都在那一刻串起来了。 下次遇到 Top K，或许可以先别急着排序，想想能不能只维护 k 个元素的最小堆。毕竟，算法题考的不只是答案，而是你是否能看到“不需要全排序”的那扇门。
热门跟贴