用堆解决 Top-k 问题：从 O(nk) 到 O(n log k) 的三级进阶（Hello 算法）

本篇技术指南以《Hello 算法》第 5 章「堆」（日文版章节 ja/docs/chapter_heap/top_k.md，中文版对应 docs/chapter_heap/top_k.md）为核心骨架展开，并佐以仓库中 Python、C++、Java、Go、C 等语言的实际实现。读者将掌握 Top-k 问题的三种解法及其适用场景，理解"为什么求前 k 大元素要维护一个大小为 k 的小顶堆"，并能在面试与工程中直接落地这套 O(n log k) 的最小堆方案。

问题定义：在一堆数里挑出前 k 大

Top-k（top-k problem）是数据与算法场景中出现频率极高的一类问题：给定一个长度为 $n$ 的未排序数组 nums，返回其中最大的 $k$ 个元素。它既可以指"静态数组一次性查询"，也可以扩展到"数据不断流入、需要实时维护前 k 大"的动态场景。

《Hello 算法》的堆章节用一个核心案例——Top-k 问题——把前面学到的堆结构与复杂度分析串成一次实战。它先给出两个"思路直白但有明显代价"的基线方案，再引出堆解法，形成清晰的复杂度对比。以下严格沿用这一主线，并同步给出仓库源码作为对照。

方法一：遍历选择——k 次扫描，代价 O(nk)

最直觉的做法正如方法一"走査による選択"（遍历选择）所示：对数组执行 $k$ 轮扫描，每一轮找出当前剩余元素中的最大值并取出，依次得到第 $1、2、\dots、k$ 大元素。

这种做法的时间复杂度为 $O(nk)$。其短板非常明显：

• 只有当 $k \ll n$（即 $k$ 远小于 $n$）时才是可接受的；
• 一旦 $k$ 逼近 $n$，复杂度就会退化为接近 $O(n^2)$，在数据量稍大时几乎不可用。

书里还特别留了一个提示（tip）：当 $k = n$ 时，这种"每轮挑一个最大、取走、再挑下一个最大"的过程恰好等价于把整个数组排成升序——这正是「选择排序（selection sort）」算法本身。换句话说，遍历选择本质上是"不完整的选择排序"，$k$ 越大它就越接近于一次完整排序。

方法二：全量排序——O(n log n)，但做了太多无用功

第二种直接做法是排序：先把整个 nums 升序排序，然后取最右端（最大）的 $k$ 个元素。

这一步的时间复杂度是 $O(n\log n)$（取决于所采用的比较排序算法，仓库中如 merge_sort、quick_sort 等均为典型实现）。

正如原文指出的那样，这种做法显然做了超过需求的工作：题目只需要最大的 $k$ 个元素是谁，其余 $n - k$ 个元素的相对顺序我们根本不关心，而排序却把它们全部排好了。这就是"全量排序"在思维上简单、在计算上浪费的根源。

方法三：最小堆——在 O(n log k) 内只维护 k 个候选

堆方法之所以高效，核心洞察是：我们不需要保存全部元素，只需要维护一个始终只含"当前见过的最大 k 个元素"的容器，并且该容器要能以很低代价回答"这 k 个里最小的是谁"，以及快速替换它。最小堆（小顶堆，min-heap）恰好同时满足这两点——堆顶即最小值。

算法流程如下（与文档步骤一一对应）：

1. 初始化一个最小堆，保证堆顶元素始终是堆内最小元素；
2. 先将数组的前 $k$ 个元素依次入堆，此时堆里恰好有 $k$ 个元素；
3. 从第 $k+1$ 个元素开始继续遍历：若当前元素大于堆顶元素，说明堆内最小的那个候选已不可能进入前 k 大，于是将堆顶出堆，再把当前元素入堆；若当前元素不大于堆顶，则直接跳过；
4. 遍历结束后，堆中保留的 k 个元素即为整个数组中最大的 k 个元素。

原文用 9 张分步示意动画化地展示了这一替换过程：

每一次出堆 + 入堆，堆内部只需沿单条路径做上浮/下滤（sift up / sift down），代价为 $O(\log k)$；全程共 $n$ 次入堆/出堆操作，堆的最大长度被限制在 $k$，因此总时间复杂度的上界为：

$$T(n) = O(n \log k)$$

这是一个非常优秀的结论：

• 当 $k$ 很小（远小于 $n$）时，$O(n \log k)$ 趋向于 $O(n)$；
• 当 $k$ 很大（逼近 $n$）时，$O(n \log k)$ 也不会超过 $O(n \log n)$，与全量排序同级。

仓库源码对照：同一思路的多种语言落地

《Hello 算法》为堆章节提供了多语言示例。下面以仓库中若干语言的 top_k_heap 实现为例（中文版代码位于 codes/python/chapter_heap/top_k.py、codes/cpp/chapter_heap/top_k.cpp、codes/java/chapter_heap/top_k.java、codes/go/chapter_heap/top_k.go、codes/c/chapter_heap/top_k.c），印证上述三步算法。

Python（利用标准库 heapq）：codes/python/chapter_heap/top_k.py

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

测试样例同样取 nums = [1, 7, 6, 3, 2]、k = 3，期望输出为最大的三个元素。

C++（标准库 priority_queue，用 greater<int> 声明小顶堆）：codes/cpp/chapter_heap/top_k.cpp

priority_queue<int, vector<int>, greater<int>> topKHeap(vector<int> &nums, int k) {
    // 初始化小顶堆
    priority_queue<int, vector<int>, greater<int>> heap;
    // 将数组的前 k 个元素入堆
    for (int i = 0; i < k; i++) {
        heap.push(nums[i]);
    }
    // 从第 k+1 个元素开始，保持堆的长度为 k
    for (int i = k; i < nums.size(); i++) {
        // 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if (nums[i] > heap.top()) {
            heap.pop();
            heap.push(nums[i]);
        }
    }
    return heap;
}

注意 C++ 的 priority_queue 默认是大顶堆，这里显式传入 greater<int> 比较器将其反转成小顶堆，从而保证 heap.top() 返回的是堆内最小元素——这正是判定"当前元素是否值得入堆"的关键。

Java（PriorityQueue 默认即小顶堆）：codes/java/chapter_heap/top_k.java

static Queue<Integer> topKHeap(int[] nums, int k) {
    // 初始化小顶堆
    Queue<Integer> heap = new PriorityQueue<Integer>();
    // 将数组的前 k 个元素入堆
    for (int i = 0; i < k; i++) {
        heap.offer(nums[i]);
    }
    // 从第 k+1 个元素开始，保持堆的长度为 k
    for (int i = k; i < nums.length; i++) {
        // 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if (nums[i] > heap.peek()) {
            heap.poll();
            heap.offer(nums[i]);
        }
    }
    return heap;
}

Go（基于 container/heap 接口自定义小顶堆）：codes/go/chapter_heap/top_k.go

func topKHeap(nums []int, k int) *minHeap {
	// 初始化小顶堆
	h := &minHeap{}
	heap.Init(h)
	// 将数组的前 k 个元素入堆
	for i := 0; i < k; i++ {
		heap.Push(h, nums[i])
	}
	// 从第 k+1 个元素开始，保持堆的长度为 k
	for i := k; i < len(nums); i++ {
		// 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
		if nums[i] > h.Top().(int) {
			heap.Pop(h)
			heap.Push(h, nums[i])
		}
	}
	return h
}

Go 需要自行实现 Len / Less / Swap / Push / Pop 以适配 heap.Interface，这段代码恰好也演示了"自建小顶堆"的最小样板（仓库中完整的大顶堆实现可进一步参考 my_heap.go）。

C（用大顶堆模拟小顶堆——元素取反技巧）：codes/c/chapter_heap/top_k.c

C 语言没有内置堆，需复用第 5 章手写的大顶堆 my_heap.c。仓库采用了一个巧妙的技巧：将待比较元素全部取相反数再存入大顶堆，从而用大顶堆等价模拟小顶堆的行为：

/* 元素入堆：取反后 push 进大顶堆，堆顶反而变成"绝对值最小" */
void pushMinHeap(MaxHeap *maxHeap, int val) {
    push(maxHeap, -val);
}

/* 元素出堆 */
int popMinHeap(MaxHeap *maxHeap) {
    return -pop(maxHeap);
}

/* 访问堆顶元素 */
int peekMinHeap(MaxHeap *maxHeap) {
    return -peek(maxHeap);
}

随后 topKHeap 的主体逻辑（先入前 k 个、再逐一遍历替换、结束时取回堆内元素）与其余语言完全一致，见 top_k.c 中的实现与 main 测试用例。这种"取反模拟"在无法直接构造比较器的语言/场景中是值得记下的通用技巧。

从源码结构看，top_k 解法被统一放置在 chapter_heap 目录下，且各语言版本均提供了可运行的 Driver/main 入口（如 top_k.py 底部直接打印结果），方便读者"一键运行"验证。

三种方法复杂度横向对比

方法	时间开销	额外空间	适用前提
遍历选择	$O(nk)$	$O(1)$	仅 $k \ll n$ 时可用；$k \to n$ 时退化接近 $O(n^2)$
全量排序	$O(n \log n)$	$O(n)$ 或 $O(1)$（视排序算法）	通用，但做了超出需求的全量排序
最小堆	$O(n \log k)$	$O(k)$	通用；$k$ 越小越接近 $O(n)$，最坏不超过 $O(n \log n)$

堆解法的另一大优势是空间占用只有 $O(k)$：无需像排序那样持有整个数组的副本或额外工作区，只需要一个长度不超过 $k$ 的堆。当 $n$ 极大（例如上亿规模的日志、埋点数据）而 $k$ 很小（例如前 10 名）时，$O(k)$ 的空间使方案可以在内存受限的环境里运行。

深入一步：为什么候选容器必须是最小堆？

这是理解整个方案的关键。设想我们要维护"当前见过的最大 k 个元素"，那么：

• 若用大顶堆存放候选，堆顶是候选中的最大者。当新元素到来时，我们无法知道它是否应该挤进前 k 大——因为我们需要淘汰的是候选中的最小者，而大顶堆恰恰不提供"快速取最小"的能力，只能线性扫描，方案退化为 $O(nk)$。
• 若用最小堆存放候选，堆顶是候选中的最小者。任何新元素只要比"候选里最弱的一个"还大，就足以淘汰堆顶并顶替其位置。每次淘汰 + 插入都是 $O(\log k)$。

换言之，"淘汰最小者"的需求天然决定了下界容器必须是小顶堆。这与常见的"求前 k 小元素则用大顶堆"互为镜像，记忆口诀就是：容器的大小固定为 k，其堆顶永远朝向"最容易被淘汰的那一端"。

动态数据流场景：Top-k 的在线维护能力

文档在结尾特别强调了堆方案对动态数据流（dynamic data stream）的天然适配：当数据持续流入、无法一次性载入内存时，"先排序再取前 k"根本无从谈起，而堆解法只需对新到的每个元素执行一次"比较 + 可能的出堆/入堆"，即可让堆内元素实时保持为截至当前的最大 k 个。

这正是 Top-k 在真实系统中高频出现的形态，例如：流式统计热门关键词、日志系统实时维护 TopN 错误、游戏排行榜的增量更新等。每次更新代价仅 $O(\log k)$，无需回溯历史数据。从这一点看，"最小堆 + 固定容量 + 淘汰堆顶"构成了一个可在线运行、可增量维护的数据结构原型，这也是《Hello 算法》将 Top-k 选作堆章节收尾案例的原因——它把堆的插入、删除、堆顶访问三类基础操作完整串成了一道具有工程价值的综合题。

小结

围绕 Top-k 问题，本篇完整复现了《Hello 算法》的递进式讲解：从 $O(nk)$ 的遍历选择（$k=n$ 时退化为选择排序），到 $O(n\log n)$ 却"大材小用"的全量排序，再到以最小堆为核心的 $O(n\log k)$ 方案。仓库中 codes/python/chapter_heap/top_k.py、codes/cpp/chapter_heap/top_k.cpp、codes/java/chapter_heap/top_k.java、codes/go/chapter_heap/top_k.go、codes/c/chapter_heap/top_k.c 等实现验证了同一算法的跨语言一致性，也展示了"为什么淘汰端决定堆序方向"的底层直觉。掌握这一模式后，读者可以顺手将其推广到"前 k 小"、流式 TopN、合并有序流等一大批衍生问题上。