LeetCode 347. 前 K 个高频元素：堆与桶排序的分工

前 K 个高频元素（LeetCode 347，Medium）是「选前 K」家族的第二课：给一个数组与整数 k，返回出现频率最高的 k 个元素。它的两段结构清晰——先计数（哈希表，无争议），再选前 K（这才是题目考的部分）：选的方案有堆与桶排序两条路线，分别代表「通用性」与「极致效率」的取舍。本篇把两条路线与「前 K 问题」的选择决策树讲清。

路线一：最小堆——O(n log k) 的通用方案

堆解法的关键洞察：要保留前 K 大（频率最高），只需维护一个大小为 K 的最小堆——堆顶是 K 个中「最小的」，新元素与堆顶比较：比堆顶大就替换堆顶（弹堆顶、入新元素），否则直接跳过。为什么用最小堆装「最大的 K 个」：最小堆的堆顶暴露的是「这 K 个中最弱的一员」——新元素只需与最弱的比较；若用最大堆，堆顶是「最强者」，无法判断新元素有没有资格入选。复杂度：计数 O(n) + n 次堆操作（每次 O(log k)）= O(n log k)——k 通常远小于 n，比全排序的 O(n log n) 优。堆的通用性优势：数据是流式的（不必一次载入全部——边读边维护堆，内存 O(k)）；比较标准任意（堆的比较函数可以自定义——按频率、按组合分数）；它是「在线的前 K」——大数据与流式场景的唯一现实选择。

import heapq
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    heap = []                          # (频率, 数字) 的最小堆，大小 ≤ k
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)        # 弹出「K 个中频率最低」的
    return [num for freq, num in heap]

Python 的便车：heapq.nlargest(k, count.keys(), key=count.get) 一行完成（内部即上述最小堆逻辑）——面试要求手写时写上面的，工程中用库。

路线二：桶排序——O(n) 的极致方案

桶排序的洞察：元素的频率范围是有限的（频率在 1 到 n 之间——n 个元素最多出现 n 次），按频率建桶：buckets[f] = 所有出现频率恰为 f 的元素列表；从高频率桶向低频率桶扫描，收集到凑满 k 个为止。复杂度：计数 O(n) + 建桶 O(n) + 扫描 O(n) = 严格 O(n)——比堆的 O(n log k) 更优。桶排序的代价：空间 O(n)（桶数组与元素列表）；以及它只适用于「取值可枚举」的场景——频率是 1..n 的整数（可枚举），所以这里可行；若要选「前 K 大的浮点数」，桶就无处安放，堆是唯一选择。两条路线的选择决策树：数据流式/内存受限/比较标准自定义 → 堆；数组一次性处理/频率可枚举/追求极致 O(n) → 桶；面试先讲堆（通用），追问优化再讲桶（惊艳）——本库《接雨水》的「多解法展示」策略在此重演。

「前 K 问题」的家族与选择决策树

前 K 家族的完整版图值得梳理。成员一：前 K 大/小的数（快速选择的 O(n) 平均——本库《第 K 个最大元素》的锤子）；成员二：前 K 个高频元素（本篇：计数 + 堆/桶）；成员三：前 K 个高频单词（加并列时的字典序 tie-break——堆的比较函数多一层）；成员四：数据流中的第 K 大（流式的持续维护——最小堆常驻，本库堆解法的流式形态）。选择决策树：数据在内存里且只要一次 → 快速选择（平均 O(n)）；数据流式或要持续维护 → 最小堆（O(n log k)，在线）；频率可枚举且追求极致 → 桶（O(n) 稳定）；面试口头表达 → 「堆是通用解，快速选择均摊更快，桶在可枚举时最极致」——一句话覆盖全家族的取舍。本篇的元教训：很多「选前 K」的问题，难点根本不在「选」，在前面的计数/统计建模——把问题拆成「统计」与「选择」两段，每段独立选最优算法，是这类题的通用解题框架。

堆的内部机制：数组如何表示一棵完全二叉树

用堆解题，值得懂堆的内部实现——堆是用数组表示的完全二叉树。数组的映射公式：下标 i 的节点，左孩子在 2i+1、右孩子在 2i+2、父节点在 (i-1)//2——完全二叉树的层序遍历恰好填满数组，无空洞（这是「完全」二叉树的名字由来）。两个核心操作：上浮（sift-up）——新元素加在数组末尾，与父节点比较，更大（最大堆）则交换上浮，直到不大为止（插入的 O(log n)）；下沉（sift-down）——堆顶被替换后，与两个孩子中较大者比较，更小则交换下沉（弹出的 O(log n)）。建堆的 O(n) 秘密：从最后一个非叶节点开始逆序下沉每个节点，数学上可证明总代价是 O(n)（多数节点下沉深度浅）——比逐个插入的 O(n log n) 快，这是「批量建堆」的正确姿势（heapq.heapify 的内部）。堆的家族成员：Python 的 heapq 是最小堆（取最小——所以「前 K 大」用它），大顶堆靠取负模拟；indexed heap（支持按句柄增删——Dijkstra 的惰性删除替代）是进阶变体。理解数组建堆的最后一个收益：堆排序的原地性（本库《排序总览》）从「数组就是树」直接推出——排序与堆，同一份数据的两种视图。

堆与有序集合的对比：什么时候不用堆

堆是「选前 K」的主力，但「有序集合」（平衡二叉搜索树，如 Python 的 sortedcontainers）在某些场景更合适——对比的分界值得画清。堆的强项：只关心「最值」与「前 K」——O(log n) 的插入与 O(1) 的最值读取；不需要全序遍历（堆的内部无序，只能弹出来看）。有序集合的强项：范围查询（「频率在 10 到 20 之间的元素」——堆做不到）、任意位置的删除（按 key 删除指定元素——堆只能删堆顶）、顺序遍历（从第 3 大开始遍历——堆必须全部弹出）。场景的选择决策：流式维护 Top-K → 堆（本篇正文的方案）；频繁的「第 k 大查询」→ 有序集合（O(log n) 的按名次访问——堆做不到）；「插入删除都频繁 + 需要最值」→ 两者皆可（堆更快、集合更全）。一个反直觉的工程事实：Python 的 sortedcontainers（纯 Python）在多数基准里比 C 实现的堆操作组合更快（列表插入的内存局部性 + 减少 Python 层函数调用）——「算法复杂度低」不等于「实测更快」，常数与语言实现的现实必须尊重——这也是为什么本库反复强调「实测校准直觉」。

堆排序的原地性分析：为什么空间 O(1)

堆排序的原地性是一个值得单独分析的工程特性。标准的堆排序在原数组上完成：建堆阶段把无序数组重排为堆结构（不需要额外空间——堆的性质由下标关系隐式定义，不需要指针）；排序阶段反复「堆顶与末尾交换 + 尺寸减一 + 下沉」——每次交换后数组的前缀仍是有效堆。整个过程中，辅助空间只有几个临时变量（交换时的暂存）——O(1) 的空间复杂度使它成为「内存极限场景」的首选排序。对比归并的 O(n) 辅助数组和快排的 O(log n) 递归栈——堆排序的空间效率是三巨头中最好的。它的实际瓶颈在于缓存的跳跃访问模式（下沉操作访问 2i+1 和 2i+2——数组的跳跃导致缓存不友好）——这也是堆排序在实测中不如快排的根本原因——不是算法差，是硬件不配合。

堆的变体扩展：双端堆与可索引堆

标准堆之外的两种实用变体值得认识。双端堆（DEPQ）：同时支持取最大与取最小——对偶堆加哨兵互指的实现方案——本库语境的同时取最高分与最低分场景。可索引堆：支持按句柄删除或更新任意元素——标准堆只能删堆顶，Dijkstra 算法里更新已入队节点的距离需要这个能力——不支持的堆只能用惰性删除。可索引堆的实现：额外维护一个句柄到数组下标的反向映射，让 update 和 delete 能定位到数组中的位置——映射的维护是它比标准堆复杂的全部原因。两个变体都是标准堆的小幅扩展——理解了标准堆的数组表示，变体的学习成本就只是多了哪些映射。

堆的「部分排序」视角

堆还有一层容易被忽略的语义：它不仅是优先队列，还是一种部分排序的状态。堆的数组里前 i 小的元素永远在数组的某个前缀结构里（堆性质保证父节点不超过子节点——但不保证兄弟间的顺序）——它排序了一半乱序了另一半——这种部分排序的状态正是它的效率来源。两种视角的实用切换：只要最值用优先队列视角；要分批取最值用部分排序视角（每弹一个堆顶就是完成一层的排序——Top-K 的 k 次弹出就是排好了前 k 名——堆的部分排序本质让 Top-K 不是堆的应用而是堆的定义）。

堆的「不分网络」优势：离线与弱网场景

堆还有一个常被忽视的工程优势：它完全离线可用——不依赖网络连接、不依赖云服务。在弱网环境（移动设备、边缘计算、离线分析）中，堆作为纯本地的数据结构没有任何外部依赖——它的所有操作都在本地内存完成，网络断连不影响任何功能。这个特性在物联网和边缘计算场景中价值突出（传感器数据的实时 Top-K 筛选不依赖云连接）。对比需要云 API 的 AI 服务（本库语境的云端大模型推理），堆是真正「随身携带」的算法——它的可用性不受网络条件的影响，也不产生任何 API 费用——这种独立性在成本敏感和可靠性敏感的场景中都是重要的加分项。

小结

这篇收成四条：最小堆装「最大的 K 个」——堆顶暴露最弱成员，新元素只与最弱者比较，O(n log k) 且支持流式与自定义比较；桶排序按频率建桶从高到低扫——严格 O(n)，代价是空间 O(n) 与「取值可枚举」的前提；前 K 家族四成员（前 K 大、前 K 频、前 K 单词、流式第 K）各有最优工具，决策树一句话覆盖；这类题的难点在前面的统计建模——「统计 + 选择」的两段式框架是通用解题法。

参考资料

• LeetCode 347. Top K Frequent Elements —— 题目与官方题解
• 本库前篇：《LeetCode 215. 数组中的第 K 个最大元素》《LeetCode 146. LRU 缓存》—— 堆与设计题的相邻篇目
• heapq 模块文档 —— Python 堆的标准工具