堆(优先队列)基础原理与题目说明

堆(优先队列)基础原理与题目说明文章目录堆(优先队列)基础原理与题目说明一、 什么是堆Heap1.1 Top K 问题核心法则二、 Python 中的堆实现与模板2.1 找第 K 大原生小顶堆模板2.2 找第 K 小取负模拟大顶堆模板三、 Top K 系列实战[215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/)[347. 前 K 个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)四、 高级应用双堆对撞设计[295. 数据流的中位数](https://leetcode.cn/problems/find-median-from-data-stream/) 查看完整专栏LeetCode基础算法专栏特别说明本文为个人的 LeetCode 刷题与学习笔记内容仅供学习与交流使用禁止转载或用于商业用途。需要强调的是文中的题目解法不一定是最优解可能存在时间或空间复杂度的进一步优化空间主要目的是分享个人的解题思路与逻辑实现仅供参考。笔记内容为个人理解与总结可能存在疏漏或偏差欢迎读者自行甄别并交流探讨。一、 什么是堆Heap堆通常作为优先队列的具体实现逻辑上是一棵完全二叉树主要分为两类大顶堆Max-Heap任意节点的值≥ \ge≥其左右孩子的值→ \rightarrow→堆顶永远是最大值。小顶堆Min-Heap任意节点的值≤ \le≤其左右孩子的值→ \rightarrow→堆顶永远是最小值。1.1 Top K 问题核心法则在算法实战中堆是解决“第 K 大/小”及“前 K 个”频率等问题的杀手锏数据结构。请牢记以下反直觉但极其高效的匹配法则目标任务选择的数据结构核心逻辑找第 K 大/ 前 K 大大小为 K 的小顶堆堆中仅保留最大的 K 个数比堆顶这K个数中最小的还小的数直接丢弃。最终堆顶即为第 K 大。找第 K 小/ 前 K 小大小为 K 的大顶堆堆中仅保留最小的 K 个数比堆顶这K个数中最大的还大的数直接丢弃。最终堆顶即为第 K 小。二、 Python 中的堆实现与模板Python 的内置库heapq默认实现的是小顶堆。2.1 找第 K 大原生小顶堆模板importheapqdeffindKthLargest(nums:list[int],k:int)-int:heap[]fornuminnums:heapq.heappush(heap,num)# 堆的大小超过 K 时弹出堆顶当前的最小值iflen(heap)k:heapq.heappop(heap)# 遍历结束堆里只剩最大的 K 个数堆顶就是第 K 大returnheap[0]2.2 找第 K 小取负模拟大顶堆模板由于 Python 没有直接提供大顶堆通用的技巧是存入相反数例如 5 变成 -5。值越大取负后越小从而完美利用原生小顶堆模拟大顶堆。importheapqdeffindKthSmallest(nums:list[int],k:int)-int:heap[]fornuminnums:# 存入相反数模拟大顶堆heapq.heappush(heap,-num)iflen(heap)k:heapq.heappop(heap)# 取出时再次取负还原真实值return-heap[0](注如果存入heapq的是元组(x1, x2)小顶堆只会默认比较元组的第一个元素x1这在处理频率等问题时非常有用。)三、 Top K 系列实战215. 数组中的第K个最大元素题目描述给定整数数组nums和整数k请返回数组中第k个最大的元素。你必须设计并实现时间复杂度为O ( n log ⁡ k ) O(n \log k)O(nlogk)的算法解决此问题。解题思路直接套用上述的“大小为 K 的小顶堆”模板。初始化空的小顶堆。对每个数字推入堆中。关键规则如果堆的大小超过k就把堆顶弹出去。遍历结束堆里只留了最大的k个数比堆顶还小的数已经在之前被丢弃了。此时堆顶即为数组的第 K 大元素。核心代码importheapqfromtypingimportListclassSolution:deffindKthLargest(self,nums:List[int],k:int)-int: 维护大小为 K 的小顶堆堆里永远只存「当前最大的 K 个数」 堆顶 这 K 个数里最小的 → 恰好就是整个数组的第 K 大元素 heap[]fornuminnums:# 入堆Python 内置的 heapq 就是小顶堆heapq.heappush(heap,num)# 堆的大小超过k弹出堆顶(这k个数中最小的)iflen(heap)k:heapq.heappop(heap)# 堆顶就是第k大returnheap[0]347. 前 K 个高频元素题目描述给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。解题思路采用哈希表Counter 小顶堆的方法解题。先用哈希表统计数组中每个数字的出现频率。维护一个大小固定为k的小顶堆堆中存储元组(频率, 数字)。heapq会自动根据元组的第一个元素即频率进行排序。频率超出限制时弹出堆顶当前频次最小的元素。最终堆中保留的就是频率最高的k个元组。核心代码importheapqimportcollectionsfromtypingimportListclassSolution:deftopKFrequent(self,nums:List[int],k:int)-List[int]:hashmapcollections.Counter(nums)heap[]fornuminhashmap:# 存储 (频率, 数字)Python 的 heapq 只比较元组的首个元素heapq.heappush(heap,(hashmap[num],num))# 保持堆的容量为 kiflen(heap)k:heapq.heappop(heap)ans[]# 将堆中剩下的元素最高频的k个数提取出来forfreq,numinheap:ans.append(num)returnans四、 高级应用双堆对撞设计295. 数据流的中位数题目描述中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。设计一个MedianFinder类支持动态地向数据流中添加元素并在O ( 1 ) O(1)O(1)时间内返回当前的中位数。解题思路我们用两个堆把数据流劈成两半实现动态的排序与中位数提取大顶堆leftheap存放数据流中较小的一半数字→ \rightarrow→堆顶 左半部分的最大值需用负号模拟。小顶堆rightheap存放数据流中较大的一半数字→ \rightarrow→堆顶 右半部分的最小值。平衡规则核心重点元素优先进入大顶堆或者根据数值大小对比后进入对应的堆。动态调整长度我们强行规定大顶堆的元素个数要么与小顶堆相等要么比小顶堆多且仅多 1 个。计算中位数总数为奇数时大顶堆比小顶堆多一个大顶堆的堆顶就是中位数。总数为偶数时两个堆大小相等两个堆顶的平均值就是中位数。核心代码importheapqclassMedianFinder:def__init__(self):# 大顶堆存较小的一半数字堆顶是左侧最大值存负数模拟self.leftheap[]# 小顶堆存较大的一半数字堆顶是右侧最小值正常存self.rightheap[]defaddNum(self,num:int)-None:# 1. 判断放在左边还是右边# 如果左堆为空或者新数字小于等于左堆的最大值放入左堆ifnotself.leftheapornum-self.leftheap[0]:heapq.heappush(self.leftheap,-num)else:heapq.heappush(self.rightheap,num)# 2. 动态平衡两个堆的长度# 规定大顶堆可以比小顶堆多1个元素但不能多2个及以上iflen(self.leftheap)len(self.rightheap)1:# 左侧多了匀一个给右侧val-heapq.heappop(self.leftheap)heapq.heappush(self.rightheap,val)# 规定大顶堆的长度绝不能小于小顶堆eliflen(self.leftheap)len(self.rightheap):# 右侧多了匀一个给左侧valheapq.heappop(self.rightheap)heapq.heappush(self.leftheap,-val)deffindMedian(self)-float:# 1. 偶数个两个堆顶取平均值iflen(self.leftheap)len(self.rightheap):ans(-self.leftheap[0]self.rightheap[0])/2.0else:# 2. 奇数个规定了左堆可以多一个所以中位数必定在左堆顶ansfloat(-self.leftheap[0])returnans# 使用说明# obj MedianFinder()# obj.addNum(num)# param_2 obj.findMedian()