【笔面试算法学习专栏】堆与优先队列实战：力扣hot100之215.数组中的第K个最大元素、347.前K个高频元素

引言与堆数据结构基础在算法设计与问题求解中堆Heap是一种极其高效的数据结构它能够在动态数据流中快速维护最值广泛应用于排序、调度、图算法等领域。堆的本质是一棵完全二叉树并满足堆序性质对于最大堆任意节点的值不小于其子节点值对于最小堆任意节点的值不大于其子节点值。这种性质使得堆的根节点始终是全局最大或最小元素从而能够在O ( 1 ) O(1)O(1)时间内获取最值。堆的典型操作及其时间复杂度如下建堆Heapify将无序数组调整为堆结构时间复杂度O ( n ) O(n)O(n)优于逐个插入的O ( n log ⁡ n ) O(n \log n)O(nlogn)。插入Push将新元素加入堆并保持堆序时间复杂度O ( log ⁡ n ) O(\log n)O(logn)。弹出Pop移除堆顶元素并调整堆时间复杂度O ( log ⁡ n ) O(\log n)O(logn)。取堆顶Top获取堆顶元素时间复杂度O ( 1 ) O(1)O(1)。在 Python 中堆通过内置模块heapq实现该模块提供基于列表的最小堆操作。需要注意的是heapq仅提供最小堆若需要最大堆可通过取相反数或自定义比较函数实现。本文将深入解析力扣hot100中两道经典堆应用题215. 数组中的第K个最大元素与347. 前K个高频元素。通过对比快速选择、哈希表、桶排序等多种解法揭示堆在TopK问题中的核心作用并提供完整可运行的代码实现与面试考点分析。215. 数组中的第K个最大元素题目概述与链接题目链接215. Kth Largest Element in an Array问题描述给定整数数组nums和整数k请返回数组中第k个最大的元素。请注意你需要找的是数组排序后的第k个最大的元素而不是第k个不同的元素。要求时间复杂度优于O ( n log ⁡ n ) O(n \log n)O(nlogn)。示例输入: nums [3,2,1,5,6,4], k 2 输出: 5 解释: 排序后数组为 [1,2,3,4,5,6]第2个最大的元素是5。核心解题思路本题有两种主流解法快速选择QuickSelect与堆解法。快速选择基于快速排序的划分思想期望时间复杂度为O ( n ) O(n)O(n)最坏情况O ( n 2 ) O(n^2)O(n2)堆解法维护一个大小为k kk的最小堆遍历数组不断更新堆最终堆顶即为第K大元素时间复杂度稳定在O ( n log ⁡ k ) O(n \log k)O(nlogk)。堆解法的核心步骤建立大小为k kk的最小堆堆顶为堆中最小元素。遍历数组前k kk个元素直接加入堆。遍历剩余元素若当前元素大于堆顶则弹出堆顶并插入当前元素。遍历结束后堆顶即为第k kk个最大元素。为什么使用最小堆因为我们要找第k kk大元素只需维护当前看到的k kk个最大元素其中最小的那个就是目标。最小堆的堆顶正好是这k kk个元素中的最小值当遇到更大的元素时替换堆顶即可保证堆中始终是当前最大的k kk个元素。复杂度分析时间复杂度建堆前k个元素O ( k ) O(k)O(k)遍历剩余n − k n-kn−k个元素每次插入与弹出最多O ( log ⁡ k ) O(\log k)O(logk)因此总时间O ( k ( n − k ) log ⁡ k ) O ( n log ⁡ k ) O(k (n-k) \log k) O(n \log k)O(k(n−k)logk)O(nlogk)。当k kk远小于n nn时效率接近O ( n ) O(n)O(n)当k kk接近n nn时退化为O ( n log ⁡ n ) O(n \log n)O(nlogn)。空间复杂度堆存储k kk个元素因此为O ( k ) O(k)O(k)。代码实现以下是使用 Python 内置heapq模块的完整实现关键代码段控制在20行以内注释详细说明每一步操作。importheapqfromtypingimportListdeffindKthLargest(nums:List[int],k:int)-int: 使用最小堆求解第K大元素 时间复杂度: O(n log k) 空间复杂度: O(k) # 边界条件检查ifnotnumsork0orklen(nums):raiseValueError(Invalid input: nums empty or k out of range)# 创建最小堆存储前k个元素min_heapnums[:k]heapq.heapify(min_heap)# O(k) 建堆# 遍历剩余元素fornuminnums[k:]:# 若当前元素大于堆顶即当前第k大的候选则替换ifnummin_heap[0]:heapq.heapreplace(min_heap,num)# 弹出最小并插入新元素O(log k)# 等价于 heapq.heappushpop(min_heap, num)# 堆顶即为第k大元素returnmin_heap[0]# 测试代码if__name____main__:nums[3,2,1,5,6,4]k2print(f第{k}大元素是:{findKthLargest(nums,k)})# 输出 5nums2[3,2,3,1,2,4,5,5,6]k24print(f第{k2}大元素是:{findKthLargest(nums2,k2)})# 输出 4代码解析heapq.heapify(min_heap)将列表原地转换为最小堆时间复杂度O ( k ) O(k)O(k)。heapq.heapreplace(min_heap, num)是高效替换操作先弹出堆顶最小再插入新元素保证堆大小不变。这比先heappop再heappush少一次调整。边界条件处理确保输入合法性避免k大于数组长度等情况。优化讨论手动建堆 vs heapq库heapq提供的是基于列表的轻量级实现适合大多数场景。若需要自定义比较逻辑如最大堆可存储(-num, num)或实现类重载__lt__。手动建堆如实现_heapify、_siftdown有助于深入理解堆调整过程但在工程中推荐使用标准库。K值大小对算法选择的影响当k kk较小时如k ≤ n / 10 k \leq n/10k≤n/10堆解法O ( n log ⁡ k ) O(n \log k)O(nlogk)非常高效。当k kk接近n nn时如k n / 2 k n/2kn/2堆解法退化为O ( n log ⁡ n ) O(n \log n)O(nlogn)此时快速选择期望O ( n ) O(n)O(n)更具优势。快速选择的最坏情况O ( n 2 ) O(n^2)O(n2)可通过随机化划分或中位数法避免但在面试中通常只需分析期望复杂度。空间优化若允许修改原数组可使用原地划分的快速选择将空间降至O ( 1 ) O(1)O(1)。堆解法空间O ( k ) O(k)O(k)不可省略但通常可接受。面试考点堆的选择为什么用最小堆而非最大堆解释“维护当前最大的k个元素”这一思路。时间复杂度推导能够详细分析建堆、插入、弹出的复杂度并对比快速选择。边界条件处理k len(nums)、k 0、空数组等情况体现代码健壮性。库函数使用是否知道heapq.heapreplace与heapq.heappushpop的区别两者在本题中效果相同但heapreplace稍快。扩展问题若数据流持续到来即在线算法如何调整此时堆解法天然支持动态更新而快速选择需要重算。347. 前K个高频元素题目概述与链接题目链接347. Top K Frequent Elements问题描述给定一个非空的整数数组nums返回其中出现频率前k高的元素。你可以按任意顺序返回答案。要求时间复杂度优于O ( n log ⁡ n ) O(n \log n)O(nlogn)。示例输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 解释: 元素1出现3次元素2出现2次前2高频元素是1和2。核心解题思路本题需要两个步骤统计频率与筛选TopK。统计频率自然使用哈希表Python 中collections.Counter时间复杂度O ( n ) O(n)O(n)。筛选TopK则有两种主流方法最小堆法维护大小为k kk的最小堆堆中存储(频率, 元素)对按频率排序。遍历频率哈希表不断更新堆最终堆中元素即为前K高频。桶排序法创建长度为n 1 n1n1的桶数组下标表示频率桶内存储该频率的所有元素。然后从高频向低频遍历桶收集前k kk个元素。堆解法时间复杂度O ( n log ⁡ k ) O(n \log k)O(nlogk)桶排序O ( n ) O(n)O(n)但需要额外空间。本文将重点分析堆解法因其更通用且易于扩展到数据流场景。堆解法的核心步骤使用Counter统计每个元素的出现次数得到频率哈希表。初始化大小为k kk的最小堆按频率比较。遍历哈希表若堆未满则直接插入若已满则比较当前频率与堆顶频率若更大则替换。遍历结束后堆中元素即为前K高频提取元素返回。复杂度分析时间复杂度统计频率O ( n ) O(n)O(n)建堆与更新最多n nn个元素进入堆每次操作O ( log ⁡ k ) O(\log k)O(logk)因此总时间O ( n log ⁡ k ) O(n \log k)O(nlogk)。整体O ( n n log ⁡ k ) O ( n log ⁡ k ) O(n n \log k) O(n \log k)O(nnlogk)O(nlogk)。空间复杂度哈希表存储m mm个不同元素最坏O ( n ) O(n)O(n)。堆存储k kk个元素O ( k ) O(k)O(k)。总空间O ( n ) O(n)O(n)。代码实现importheapqfromcollectionsimportCounterfromtypingimportListdeftopKFrequent(nums:List[int],k:int)-List[int]: 使用最小堆求解前K高频元素 时间复杂度: O(n log k) 空间复杂度: O(n) ifnotnumsork0:return[]# 1. 统计频率freq_mapCounter(nums)# O(n)# 2. 构建最小堆堆中元素为 (频率, 值)按频率排序min_heap[]fornum,freqinfreq_map.items():iflen(min_heap)k:heapq.heappush(min_heap,(freq,num))# 堆未满直接插入else:# 堆已满若当前频率大于堆顶频率则替换iffreqmin_heap[0][0]:heapq.heapreplace(min_heap,(freq,num))# 3. 提取堆中的元素值return[numforfreq,numinmin_heap]# 测试代码if__name____main__:nums[1,1,1,2,2,3]k2print(f前{k}高频元素:{topKFrequent(nums,k)})# 输出 [2, 1] 或 [1, 2] 顺序不限nums2[1]k21print(f前{k2}高频元素:{topKFrequent(nums2,k2)})# 输出 [1]代码解析Counter(nums)快速统计频率返回字典{元素: 频率}。堆中存储元组(频率, 元素)Python 比较元组时按第一个元素频率排序因此堆顶是频率最小的元素。heapq.heapreplace同样用于高效替换保证堆大小不超过k kk。最终返回时只需提取元素值频率信息不再需要。优化讨论桶排序作为替代当元素频率范围明确且较小如频率不超过n nn时桶排序可将时间复杂度降至O ( n ) O(n)O(n)。具体步骤统计频率哈希表。创建长度为n 1 n1n1的桶数组下标i ii存储所有频率为i ii的元素。从下标n nn到0 00逆序遍历桶收集元素直到达到k kk个。桶排序代码更简洁但需要额外O ( n ) O(n)O(n)空间存储桶且当频率分布极端时如所有元素频率为1桶的利用率低。相同频率元素的处理题目允许按任意顺序返回但若要求相同频率时按元素大小排序则需在堆中增加二级比较。例如堆存储(频率, -元素)或自定义类。当K接近n时的优化若k kk与不同元素数量m mm接近如k ≥ m / 2 k \geq m/2k≥m/2可考虑使用最大堆将全部m mm个元素加入最大堆然后弹出前k kk个时间复杂度O ( m log ⁡ m ) O(m \log m)O(mlogm)在m mm较小时可能更优。但通常m mm与n nn同阶因此最小堆法更稳健。面试考点数据结构组合哈希表与堆的结合是经典模式能否清晰说明各自作用堆中存储内容为什么存(频率, 元素)而非(元素, 频率)解释元组比较规则。时间复杂度分析区分统计频率与筛选TopK两部分的复杂度并说明为什么总时间是O ( n log ⁡ k ) O(n \log k)O(nlogk)。边界与异常处理k 不同元素数量的情况此时返回所有元素以及空输入。扩展场景若数据是流式到达无法一次统计全量频率如何设计算法此时需使用空间节省的计数器如Count-Min Sketch配合堆。总结与扩展通过以上两道力扣hot100题目的深度解析我们揭示了堆优先队列在TopK问题中的核心作用。堆能够以O ( n log ⁡ k ) O(n \log k)O(nlogk)的时间复杂度高效维护动态数据流中的最值相比全排序O ( n log ⁡ n ) O(n \log n)O(nlogn)在k kk较小时有明显优势。关键在于选择适当的堆类型最小堆用于维护最大K个元素最大堆用于维护最小K个元素以及合理控制堆大小。堆的其他经典应用场景合并K个有序链表LeetCode 23使用最小堆存储每个链表的当前头节点每次弹出堆顶并插入该节点的下一个节点时间复杂度O ( n log ⁡ k ) O(n \log k)O(nlogk)。数据流的中位数LeetCode 295使用一个最大堆存储较小一半数一个最小堆存储较大一半数保证两堆大小平衡可在O ( log ⁡ n ) O(\log n)O(logn)时间内插入并O ( 1 ) O(1)O(1)查询中位数。任务调度操作系统中的优先队列调度、定时任务管理等。图算法Dijkstra最短路径算法、Prim最小生成树算法中都需要堆来高效选取最小边。进阶学习资源斐波那契堆Fibonacci Heap支持合并、减值等操作的理论最优数据结构但实现复杂常用于理论分析。二项堆Binomial Heap支持高效合并的另一种堆结构是斐波那契堆的基础。左偏树Leftist Tree可合并堆的一种简单实现适合函数式编程环境。实战练习力扣上标签为“堆”的题目约80道建议按难度递增顺序刷题巩固堆的应用技巧。面试高频总结在算法面试中堆相关题目通常考察以下几点能否识别出TopK模式当问题涉及“前K个最大/最小”、“第K个最值”时优先考虑堆解法。复杂度估算清晰分析建堆、插入、弹出的时间复杂度并与排序、快速选择等方法对比。代码实现细节熟练使用语言提供的堆库如Pythonheapq正确处理边界与异常。扩展思维能够讨论数据流、海量数据外排序等变种场景的解决方案。堆作为一种基础而强大的数据结构其思想贯穿于算法设计的许多领域。掌握堆不仅有助于通过技术面试更能提升实际工程中处理大数据、实时流的能力。希望本文的深度解析与代码实现能为你的算法学习之路提供坚实助力。