第 9 课：堆（Heap）—— 解决 Top K 问题的神器，优先级队列的底层实现

这是面试绝对高频考点没有之一。几乎所有 找前 K 个最大 / 最小元素 的问题最优解都是堆。这一课你会明白堆是专门为 快速获取最值 这个单一需求设计的数据结构它用最简单的结构实现了最极致的性能。一、先想明白为什么要有堆我们先回顾一下已有的数据结构获取最值的效率无序数组找最值 O (n)插入 O (1)有序数组找最值 O (1)插入 O (n)二叉搜索树平均 O (logn)最坏 O (n)且不能保证每次都最快取最值有没有一种数据结构专门用来快速获取最值同时插入和删除最值的效率也很高堆就是为这个需求而生的。它能做到获取最值O (1)插入元素O (logn)删除最值O (logn)二、堆的本质用数组实现的完全二叉树✅ 核心思想刻在脑子里堆是一棵完全二叉树且满足堆性质任意一个父节点的值都大于等于大顶堆或小于等于小顶堆它的所有子节点的值。堆的底层永远用数组实现因为完全二叉树可以完美地用数组存储没有任何空间浪费。生活化类比堆就像医院的急诊优先级队列最紧急的病人永远在最前面堆顶新来的病人会根据病情严重程度插入到合适的位置最紧急的病人被送走后剩下的病人中最紧急的会自动升到最前面基本概念大顶堆任意父节点的值 ≥ 所有子节点的值堆顶是最大值小顶堆任意父节点的值 ≤ 所有子节点的值堆顶是最小值最最重要的完全二叉树的数组表示这是堆所有操作的基础必须背下来如果一个节点在数组中的下标是i那么它的左子节点下标2*i 1它的右子节点下标2*i 2它的父节点下标(i - 1) // 2举个例子plaintext数组[5, 3, 4, 1, 2] 对应的完全二叉树 5 / \ 3 4 / \ 1 2根节点 5 的下标是 0左子节点 3 的下标是 1右子节点 4 的下标是 2节点 3 的左子节点 1 的下标是 3右子节点 2 的下标是 4节点 2 的父节点下标是 (4-1)//21正确三、堆的两个核心操作上浮和下沉所有堆的操作插入、删除、建堆都是基于这两个基本操作。1. 上浮Sift Up适用场景插入元素时使用。新元素先放在数组末尾堆的最后一个位置然后不断和父节点比较如果不符合堆性质就和父节点交换直到符合堆性质为止。代码小顶堆python运行def sift_up(heap, index): while index 0: parent (index - 1) // 2 if heap[index] heap[parent]: # 不符合小顶堆性质交换 heap[index], heap[parent] heap[parent], heap[index] index parent else: break2. 下沉Sift Down适用场景删除堆顶元素时使用。把堆的最后一个元素移到堆顶然后不断和它的两个子节点比较和最小小顶堆或最大大顶堆的那个子节点交换直到符合堆性质为止。代码小顶堆python运行def sift_down(heap, index, heap_size): while True: left 2 * index 1 right 2 * index 2 smallest index if left heap_size and heap[left] heap[smallest]: smallest left if right heap_size and heap[right] heap[smallest]: smallest right if smallest index: break heap[index], heap[smallest] heap[smallest], heap[index] index smallest✅ 两个操作的时间复杂度都是O(logn)因为最多走树的高度。四、建堆O (n) 时间复杂度最优方法自底向上的下沉法从最后一个非叶子节点开始从后往前对每个节点执行下沉操作。最后一个非叶子节点的下标(n//2) - 1代码小顶堆python运行def build_heap(arr: list) - None: 从数组构建最小堆小顶堆 优化点 1. 添加类型注解提升可读性 2. 处理边界情况空数组/单元素数组 3. 使用更清晰的循环范围 4. 添加性能关键注释 5. 优化变量命名 时间复杂度O(n) - 数学上严格证明的线性时间 空间复杂度O(1) - 原地操作 n len(arr) # 处理边界情况空数组或单元素数组不需要建堆 if n 1: return # 从最后一个非叶子节点开始索引 n//2 - 1 # 为什么是 n//2 - 1 # - 最后一个节点索引为 n-1 # - 其父节点索引 (n-1-1)//2 (n-2)//2 n//2 - 1 # 从后往前遍历确保子树先满足堆性质 for i in range(n // 2 - 1, -1, -1): _sift_down(arr, i, n) def _sift_down(heap: list, index: int, heap_size: int) - None: 向下调整堆私有方法避免命名冲突 优化点 1. 移除不必要的中间变量 2. 使用更清晰的条件判断 3. 添加边界检查注释 while True: left 2 * index 1 # 提前检查左子节点是否存在避免计算右子节点 if left heap_size: break right left 1 # 右子节点 左子节点 1减少一次乘法运算 smallest index # 检查左子节点 if heap[left] heap[smallest]: smallest left # 检查右子节点仅当右子节点存在时 if right heap_size and heap[right] heap[smallest]: smallest right # 如果不需要调整提前终止 if smallest index: break # 交换并继续下沉 heap[index], heap[smallest] heap[smallest], heap[index] index smallest✅ 非常重要建堆的时间复杂度是 O (n)不是 O (nlogn)。这是数学上严格证明的结论面试经常考。五、堆的四大经典应用场景面试必考1. 优先级队列这是堆最主要的应用。所有需要 优先级高的先执行 的场景都用优先级队列实现。操作系统的进程调度消息队列的优先级消息任务调度系统2. Top K 问题最核心求数组中前 K 个最大元素用小顶堆求数组中前 K 个最小元素用大顶堆3. 堆排序利用堆的性质进行排序时间复杂度 O (nlogn)空间复杂度 O (1)。4. 合并 K 个有序链表这是堆的经典应用比其他方法效率高得多。六、经典例题必做例题 1LeetCode 215. 数组中的第 K 个最大元素面试出现频率 100%题目给定整数数组nums和整数k请返回数组中第k个最大的元素。最优思路小顶堆维护一个大小为 k 的小顶堆遍历数组中的每个元素如果堆的大小小于 k直接加入堆如果堆的大小等于 k且当前元素大于堆顶元素就弹出堆顶加入当前元素遍历结束后堆顶元素就是第 k 个最大元素为什么用小顶堆而不是大顶堆小顶堆的堆顶是堆中最小的元素也就是 前 k 个最大元素中最小的那个正好是第 k 个最大元素时间复杂度 O (nlogk)比排序的 O (nlogn) 快得多尤其是当 n 很大而 k 很小时代码python运行import heapq def findKthLargest(nums, k): 找到数组中第 k 个最大的元素 :param nums: 整数数组 :param k: 第 k 大的元素k 从 1 开始计数 :return: 第 k 个最大元素 heap [] # 初始化小顶堆 for num in nums: # 将当前元素加入堆 heapq.heappush(heap, num) # 如果堆的大小超过 k弹出堆顶最小元素 if len(heap) k: heapq.heappop(heap) # 堆顶元素就是第 k 个最大元素 return heap[0] # 测试示例 if __name__ __main__: # 示例 1: [3,2,1,5,6,4] 中第 2 大的元素 nums1 [3, 2, 1, 5, 6, 4] k1 2 print(f示例 1: 数组 {nums1}, k{k1} → 第 {k1} 大元素 {findKthLargest(nums1, k1)}) # 输出: 5 # 示例 2: [3,2,3,1,2,4,5,5,6] 中第 4 大的元素 nums2 [3, 2, 3, 1, 2, 4, 5, 5, 6] k2 4 print(f示例 2: 数组 {nums2}, k{k2} → 第 {k2} 大元素 {findKthLargest(nums2, k2)}) # 输出: 4 # 示例 3: [1] 中第 1 大的元素 nums3 [1] k3 1 print(f示例 3: 数组 {nums3}, k{k3} → 第 {k3} 大元素 {findKthLargest(nums3, k3)}) # 输出: 1 # 示例 4: [2,1] 中第 2 大的元素 nums4 [2, 1] k4 2 print(f示例 4: 数组 {nums4}, k{k4} → 第 {k4} 大元素 {findKthLargest(nums4, k4)}) # 输出: 1✅ 记住Python 中的heapq模块实现的是小顶堆。如果需要大顶堆可以把所有元素取负数然后用小顶堆。例题 2LeetCode 347. 前 K 个高频元素题目给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。核心思路先用哈希表统计每个元素出现的频率然后用小顶堆维护频率前 k 高的元素代码python运行import heapq from collections import Counter def topKFrequent(nums, k): 返回数组中出现频率前 k 高的元素 :param nums: 整数数组 :param k: 需要返回的高频元素个数 :return: 出现频率前 k 高的元素列表 # 1. 使用 Counter 统计每个元素的频率 freq Counter(nums) # 2. 创建小顶堆存储 (频率, 元素) 对 heap [] # 3. 遍历频率字典 for num, count in freq.items(): # 将 (频率, 元素) 推入堆中 heapq.heappush(heap, (count, num)) # 4. 如果堆大小超过 k弹出频率最小的元素 if len(heap) k: heapq.heappop(heap) # 5. 提取堆中的元素注意堆中存储的是 (频率, 元素)我们只需要元素 return [num for count, num in heap] # 测试示例 if __name__ __main__: # 示例 1: [1,1,1,2,2,3] 中前 2 高频元素 nums1 [1, 1, 1, 2, 2, 3] k1 2 print(f示例 1: 数组 {nums1}, k{k1} → 前 {k1} 高频元素 {topKFrequent(nums1, k1)}) # 输出: [1, 2] 或 [2, 1]顺序不重要因为题目不要求顺序 # 示例 2: [1] 中前 1 高频元素 nums2 [1] k2 1 print(f示例 2: 数组 {nums2}, k{k2} → 前 {k2} 高频元素 {topKFrequent(nums2, k2)}) # 输出: [1] # 示例 3: [1,2,2,3,3,3,4,4,4,4] 中前 2 高频元素 nums3 [1, 2, 2, 3, 3, 3, 4, 4, 4, 4] k3 2 print(f示例 3: 数组 {nums3}, k{k3} → 前 {k3} 高频元素 {topKFrequent(nums3, k3)}) # 输出: [3, 4] 或 [4, 3] # 示例 4: [4,1,-1,2,-1,2,3] 中前 2 高频元素含负数 nums4 [4, 1, -1, 2, -1, 2, 3] k4 2 print(f示例 4: 数组 {nums4}, k{k4} → 前 {k4} 高频元素 {topKFrequent(nums4, k4)}) # 输出: [-1, 2] 或 [2, -1] # 示例 5: [5,3,1,1,1,7,7,7] 中前 2 高频元素多个相同频率 nums5 [5, 3, 1, 1, 1, 7, 7, 7] k5 2 print(f示例 5: 数组 {nums5}, k{k5} → 前 {k5} 高频元素 {topKFrequent(nums5, k5)}) # 输出: [1, 7] 或 [7, 1]1和7频率相同都出现3次例题 3LeetCode 23. 合并 K 个升序链表题目给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。核心思路把每个链表的头节点加入小顶堆每次弹出堆顶的最小节点加入结果链表如果这个节点还有下一个节点就把下一个节点加入堆重复直到堆为空代码python运行import heapq from typing import List, Optional # 定义链表节点 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next # 为调试方便添加 __str__ 方法 def __str__(self): return f{self.val} - {self.next} if self.next else f{self.val} def mergeKLists(lists: List[Optional[ListNode]]) - Optional[ListNode]: 合并 K 个升序链表 :param lists: 包含 K 个升序链表的列表 :return: 合并后的升序链表头节点 # 创建虚拟头节点避免处理空链表的边界情况 dummy ListNode(0) cur dummy # 创建小顶堆存储 (节点值, 链表索引, 节点) heap [] # 将每个非空链表的头节点加入堆 for i, head in enumerate(lists): if head: # 使用 (val, index, node) 三元组避免直接比较节点对象 heapq.heappush(heap, (head.val, i, head)) # 当堆不为空时持续合并 while heap: # 弹出最小值节点 val, idx, node heapq.heappop(heap) # 将该节点加入结果链表 cur.next node cur cur.next # 如果该节点还有下一个节点将其加入堆 if node.next: heapq.heappush(heap, (node.next.val, idx, node.next)) return dummy.next # 辅助函数创建链表 def create_linked_list(nums): 从列表创建链表 if not nums: return None head ListNode(nums[0]) cur head for num in nums[1:]: cur.next ListNode(num) cur cur.next return head # 辅助函数链表转列表 def linked_list_to_list(head): 将链表转换为列表用于测试验证 result [] while head: result.append(head.val) head head.next return result # 测试示例 if __name__ __main__: # 示例 1: [[1,4,5],[1,3,4],[2,6]] lists1 [ create_linked_list([1, 4, 5]), create_linked_list([1, 3, 4]), create_linked_list([2, 6]) ] result1 mergeKLists(lists1) print(f示例 1: 合并 [[1,4,5],[1,3,4],[2,6]] → {linked_list_to_list(result1)}) # 输出: [1, 1, 2, 3, 4, 4, 5, 6] # 示例 2: [[]] lists2 [] result2 mergeKLists(lists2) print(f示例 2: 合并 [] → {linked_list_to_list(result2)}) # 输出: [] # 示例 3: [[], [1]] lists3 [ None, create_linked_list([1]) ] result3 mergeKLists(lists3) print(f示例 3: 合并 [[], [1]] → {linked_list_to_list(result3)}) # 输出: [1] # 示例 4: [[1,2,3], [4,5,6], [7,8,9]] lists4 [ create_linked_list([1, 2, 3]), create_linked_list([4, 5, 6]), create_linked_list([7, 8, 9]) ] result4 mergeKLists(lists4) print(f示例 4: 合并 [[1,2,3],[4,5,6],[7,8,9]] → {linked_list_to_list(result4)}) # 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9] # 示例 5: [[1,1,1], [2,2], [3]] lists5 [ create_linked_list([1, 1, 1]), create_linked_list([2, 2]), create_linked_list([3]) ] result5 mergeKLists(lists5) print(f示例 5: 合并 [[1,1,1],[2,2],[3]] → {linked_list_to_list(result5)}) # 输出: [1, 1, 1, 2, 2, 3]七、常见误区堆不是完全有序的它只保证父节点比子节点大 / 小不保证左右子节点的大小关系建堆的时间复杂度是 O (n)不是 O (nlogn)求前 K 大用小顶堆求前 K 小用大顶堆不要搞反了Python 的 heapq 是小顶堆需要大顶堆时对元素取负数