力扣热题100堆专题：优先级队列、TopK与数据流中位数模板详解

力扣热题100里“堆”这个标签下的题目数量不算多但每一道几乎都是面试高频题。我见过太多人刷到这里开始卡壳要么把堆和JVM内存里的heap当成一回事跑去调编译器堆空间要么一看到PriorityQueue就不知道怎么用TopK题想不明白堆顶该放什么。今天这篇不聊别的就专攻力扣热题100里的堆专题把底层原理、常见题型、代码模板和踩坑经验一次讲透。适合正在按题单刷题的人也适合面试前想快速梳理堆题套路的人。先给一个反直觉的结论堆题看着花样多本质只有一个——在动态集合里高效取最值。只要抓住这一点热题100里的堆题可以归成三类每类记住一个模板后面解题会顺很多。1. 先分清两件“堆”刷题堆和内存堆到底差在哪很多读者看到“堆”字第一反应可能是之前遇到的那个报错java.lang.OutOfMemoryError: Java heap space然后去IDE里把编译进程堆大小调到8000MB发现还是报错。这是两个完全不同的“堆”。内存模型里的堆是JVM用来分配对象的内存区调整堆大小是为了不让运行时把内存耗尽而算法题里的堆是个数据结构全称叫二叉堆底层是数组上层逻辑是一棵完全二叉树。它专门负责一件事在大批数据里快速找出当前最大或最小的值。如果你刷的是C还会遇到另一种“堆”操作系统内存布局里malloc/new动态分配的内存来自堆区与之相对的栈区用于函数调用。这个“堆”也跟数据结构堆无关。很多人刷题群里问“堆和栈的区别”其实要区分的是两套概念数据结构领域栈LIFO和堆优先队列内存区域领域栈区局部变量和堆区动态内存在力扣热题100题单里归类到“堆”的题目基本都是在说数据结构堆。你不需要先学JVM调优也不需要管Xms/Xmx参数你只需要会用语言里现成的优先级队列API或者能手写一个二叉堆就够了。这个认知一旦打通后面所有题都不会跑偏。我见过有朋友在刷“数组中的第K个最大元素”时先去查JVM堆大小怎么设置折腾一下午最后发现题目要求根本不是这个。先分清概念比多刷十道题都重要。2. 热题100的堆题考来考去本质就是这三类场景把热题100和常见高频题单里的堆题放在一起看数量不算多但几乎每一道都能落到下面三类场景里。2.1 场景一动态数据流里随时取最值代表题是“数据流的中位数”。这题难在不是给你一个静态数组排完序就完事而是不断有新的数进来每次调用都要立刻返回当前所有数的中位数。如果每次重新排序复杂度是O(N logN)数据量一大就扛不住。用堆可以做到插入O(logN)、取中位数O(1)。核心思路是维护两个堆一个大顶堆存较小的一半数一个小顶堆存较大的一半数。只要保证两个堆的元素个数相差不超过1中位数就一定和两个堆顶有关。这种场景的共同点是数据是动态的查询是频繁的。排序做不到“每次从增量数据里快速拿到最值”而堆天生支持。2.2 场景二从N个元素里找最大或最小的K个代表题有“数组中的第K个最大元素”“前K个高频元素”。最直觉的做法是全排序取前K复杂度O(N logN)。但当N很大、K很小的时候堆可以把复杂度降到O(N logK)。具体做法是维护一个大小为K的堆。要找最大的K个元素就用小顶堆堆顶是当前K个候选里最小的遍历新元素如果它比堆顶大就替换堆顶堆会重新调整。最终堆里留下的就是最大的K个堆顶就是第K个最大。很多人会把这里的最小堆/最大堆搞反。我后面专门写一节讲这个坑这里先记住口诀找最大K个用小顶堆找最小K个用大顶堆。2.3 场景三多个有序序列的归并代表题是“合并K个升序链表”。暴力做法是每次比较K个链表的头节点取最小复杂度O(NK)K一大就很慢。把K个头节点放进堆里每次弹出一个节点再把该节点的下一个节点入堆取最小只用O(logK)总复杂度O(N logK)。堆的价值永远落在“最值”二字上。读题时只要发现需要“动态最值”“前K个”“多路归并”就应该立刻想到优先级队列。为什么不直接用平衡树因为STL的set/map、Java的TreeSet虽然也能动态取最值但实现复杂、常数较大而且处理重复元素很麻烦。堆虽然不支持快速查找但在“只关心极值或前K个”的场景下恰好够用代码更短。面试中说到堆考官也默认你会用优先级队列。3. 手撕堆的底层数组、上浮下沉和线性建堆很多刷题老手都会建议直接用heapq或PriorityQueue但我还是建议你至少手写一遍堆。因为只有理解了底层你才能解释清楚为什么比较器会写反为什么最大堆要取负数为什么heapify是O(N)。这些是面试官最爱追问的点。3.1 用数组表示的完全二叉树堆的底层是数组但逻辑上是一棵完全二叉树。对于下标i从0开始左孩子是2*i1右孩子是2*i2父节点是(i-1)//2。为什么必须是完全二叉树因为只有完全二叉树才能保证数组连续存储并且用下标直接跳父子关系。插入新元素时直接放在数组末尾再调整值的位置不需要调整指针也就不用建真正的树结构。3.2 上浮sift_up与下沉sift_down堆的核心操作就两个上浮sift_up插入新元素时先把元素放到数组末尾然后不断和父节点比较如果违反堆序就交换直到满足为止。下沉sift_down删除堆顶或替换堆顶时把新值从根节点开始和左右孩子中更小最小堆或更大最大堆的那个比较如果违反堆序就交换持续下沉。以下是一个最简最小堆的Python手写模板建议你能默写出来class MinHeap: def __init__(self): self.a [] def push(self, x): self.a.append(x) i len(self.a) - 1 while i 0: p (i - 1) // 2 if self.a[p] self.a[i]: break self.a[p], self.a[i] self.a[i], self.a[p] i p def pop(self): if not self.a: return None top self.a[0] last self.a.pop() if self.a: self.a[0] last i 0 n len(self.a) while True: l 2 * i 1 r 2 * i 2 smallest i if l n and self.a[l] self.a[smallest]: smallest l if r n and self.a[r] self.a[smallest]: smallest r if smallest i: break self.a[i], self.a[smallest] self.a[smallest], self.a[i] i smallest return top注意pop时不能简单把最后一个元素放到开头后对整个数组heapify那是O(N)正确做法是只做一次下沉O(logN)。3.3 heapify线性建堆为什么是O(N)面试官经常问给你一个数组如何原地建堆逐个插入是O(N logN)但heapify可以从最后一个非叶子节点开始逐个执行sift_down总代价是O(N)。简单解释最后一层节点最多但下沉次数为0越往上节点数越少但下沉次数越多。把所有“节点数×下沉次数”加起来是一个收敛的等比数列最终结果就是O(N)。如果你不想背推导记住这个结论也够用但能说出“越往下节点越多但下沉越少”这个理由更好。手写堆还有一个好处当你用Python的heapq遇到负数最大堆的诡异行为时你能瞬间反应过来本质上就是比较逻辑变了而不是库出了问题。4. 用熟优先级队列API比手写堆快三倍刷题时我一般直接用封装好的API手写堆只用来应对面试追问。Python用heapqJava用PriorityQueue两者的默认行为、常见技巧和坑不太一样。4.1 Python的heapqheapq默认是最小堆核心方法就几个heapify(list)原地建堆。heappush(heap, item)插入。heappop(heap)弹出堆顶。heapreplace(heap, item)先弹出堆顶再插入新元素。heappushpop(heap, item)先插入再弹出堆顶。nlargest(k, iterable)/nsmallest(k, iterable)一次取前K大/前K小。最大堆的通用技巧是取负数插入时存入-x弹出时再-回来。如果堆里存的是自定义对象就要用元组技巧例如(-priority, value)这样堆会先按-priority比较再按value比较。import heapq # 最大堆示例前K个高频元素 from collections import Counter def topKFrequent(nums, k): freq Counter(nums) heap [] for num, cnt in freq.items(): if len(heap) k: heapq.heappush(heap, (cnt, num)) elif cnt heap[0][0]: heapq.heapreplace(heap, (cnt, num)) return [num for cnt, num in heap]这里有一个易错点heap内部并不是严格降序或升序它只保证堆顶是最大或最小。最终返回的列表顺序是任意的题目通常不要求顺序但如果要按频率排序需要再处理。4.2 Java的PriorityQueueJava的PriorityQueue默认是最小堆可以这样创建// 默认最小堆 PriorityQueueInteger minHeap new PriorityQueue(); // 最大堆 PriorityQueueInteger maxHeap new PriorityQueue(Collections.reverseOrder()); // 自定义比较器按字符串长度 PriorityQueueString byLength new PriorityQueue((a, b) - a.length() - b.length());核心方法对应关系操作Java方法复杂度插入offer(e)O(logN)弹出堆顶poll()O(logN)查看堆顶peek()O(1)删除任意元素remove(e)O(N)Java的PriorityQueue有三个坑要特别注意迭代顺序不保证有序只有poll()时才保证从小到大依次弹出。自定义对象必须提供Comparator否则直接入堆会抛ClassCastException。remove(Object)的复杂度是O(N)不是O(logN)如果需要在堆中删除非堆顶元素要考虑懒删除。4.3 Python和Java的对比维度Python heapqJava PriorityQueue默认堆类型最小堆最小堆最大堆实现存入负数Collections.reverseOrder()自定义比较定义__lt__或用元组传入Comparator建堆heapify()O(N)new PriorityQueue(collection)迭代顺序不保证有序不保证有序单说刷题Python的heapq写起来更短但Java的PriorityQueue在TopK模板里也比较直接。关键是不要每次查API单词把这几行代码背下来能省大量时间。5. 三道高频堆题完整拆解思路、代码与复杂度下面这三道题覆盖了前面讲的三个场景。每道题我都给出可运行的模板你在力扣热题100里看到类似题时可以直接套。5.1 数组中的第K个最大元素这是TopK场景最经典的题。维护一个大小为K的小顶堆遍历数组如果当前元素比堆顶大就替换堆顶。最后堆顶就是第K大。import heapq def findKthLargest(nums, k): heap nums[:k] heapq.heapify(heap) for x in nums[k:]: if x heap[0]: heapq.heapreplace(heap, x) return heap[0]这里用heapreplace而不是heappop加heappush因为前者只做一次下沉后者要做一次下沉和一次上浮虽然复杂度都是O(logK)但常数更小。复杂度时间复杂度O(N logK)空间复杂度O(K)。对比排序O(N logN)当K远小于N时优势明显。5.2 前K个高频元素这题先统计频率再用堆按频率维护前K个。因为堆里存的是元组(频率, 元素)默认先比较频率正好满足要求。from collections import Counter import heapq def topKFrequent(nums, k): freq Counter(nums) heap [] for num, cnt in freq.items(): if len(heap) k: heapq.heappush(heap, (cnt, num)) elif cnt heap[0][0]: heapq.heapreplace(heap, (cnt, num)) return [num for cnt, num in heap]复杂度同样是O(N logK)。如果要按频率从高到低输出可以对堆内元素再排序不过很多题目不要求顺序。5.3 数据流的中位数这题是双堆场景的代表。两个堆的平衡关系是核心small最大堆存较小的一半Python中存入负数实现。large最小堆存较大的一半。插入时先放入small当small堆顶大于large堆顶时就做一次调整然后保证两个堆长度差不超过1。最终中位数只和两个堆顶相关。import heapq class MedianFinder: def __init__(self): self.small [] # 最大堆存较小的一半 self.large [] # 最小堆存较大的一半 def addNum(self, num: int) - None: heapq.heappush(self.small, -num) if self.small and self.large and -self.small[0] self.large[0]: val -heapq.heappop(self.small) heapq.heappush(self.large, val) if len(self.small) len(self.large) 1: val -heapq.heappop(self.small) heapq.heappush(self.large, val) if len(self.large) len(self.small) 1: val heapq.heappop(self.large) heapq.heappush(self.small, -val) def findMedian(self) - float: if len(self.small) len(self.large): return -self.small[0] if len(self.large) len(self.small): return self.large[0] return (-self.small[0] self.large[0]) / 2插入复杂度O(logN)取中位数O(1)。这个模板在面试中基本属于必背尤其是small里存负数的处理写不出来的话后面随意加变形都容易崩。5.4 合并K个升序链表多路归并场景。把每个链表的头节点入堆弹出最小值后再把该节点的下一个节点入堆。堆里不能直接存ListNode否则Python会因为没有__lt__而报错所以要存三元组(val, index, node)。import heapq def mergeKLists(lists): heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy ListNode(0) cur dummy while heap: val, i, node heapq.heappop(heap) cur.next node cur cur.next if node.next: heapq.heappush(heap, (node.val, i, node.next)) return dummy.next复杂度O(N logK)N是所有节点总数。这里存i是为了避免当val相同时Python继续比较node对象而报错。这是一个非常容易被忽视的坑。6. 堆题最容易翻车的细节和一套避坑自查清单最后把我在刷堆题过程中踩过、也看别人踩过的坑集中列出来。这些问题光看书看不出来全是实际运行代码后才会发现的。6.1 找最大K个用最小堆还是最大堆方向搞反是最常见的错误。找第K大时维护的是大小为K的最小堆堆顶是当前K个候选中最小的那个这样才能把更大的元素留在堆里。如果你用最大堆堆顶永远最大新来的元素很难比它大最终堆里留的是前K个先到的元素错得离谱。记住求最大K个用小顶堆淘汰堆顶求最小K个用大顶堆淘汰堆顶。6.2 Python负数最大堆的边界问题Python里实现最大堆最直接的方法是存负数但要注意值范围。如果是整数-10小于-5堆顶是最小的负数也就是原来的最大值没问题。但如果值是浮点数或者你需要同时存多个属性负数技巧容易乱。推荐统一用元组(-priority, value)。这样堆先比较-priority再比较value逻辑清晰很多。6.3 自定义对象入堆必须能比较Python直接用heapq存自定义类对象时类必须实现__lt__否则会抛TypeError: not supported。Java则必须在构造PriorityQueue时传入比较器。这不是可选项是必须项。一个实用习惯与其给节点写__lt__不如在堆里存元组把比较字段放在第一位。比如链表节点存(node.val, index, node)这样永不出错。6.4 堆的删除操作不是O(logN)堆只支持堆顶的O(logN)删除。如果你要删除堆里任意一个元素无论是Python的heap.remove()还是Java的remove(object)都是O(N)的。如果题目需要在特定时机删除某个值优先考虑懒删除不真正删除而是用另一个计数结构标记它失效弹出时再跳过。6.5 heapreplace和heappushpop别选错这两个操作看起来很相似实际有区别heapreplace(heap, item)先pop再push适合“新元素一定更大的TopK场景”。heappushpop(heap, item)先push再pop适合“新元素不一定更大但需要保持堆大小不变”的场景。用错了会导致堆大小变化或结果偏差。我习惯在TopK循环里用heapreplace因为它只做一次调整常数更小。6.6 堆题自查清单检查项正确做法容易犯的错堆类型求最大K用小顶堆求最小K用大顶堆反着用最大堆实现Python存负数Java用reverseOrder忘记取反Python自定义对象堆里存元组或实现__lt__直接存对象Java自定义对象提供Comparator忘传比较器堆的迭代顺序只有堆顶有序用迭代器当排序结果删除任意元素懒删除或O(N)误以为O(logN)双堆平衡插入后检查堆顶关系和长度差只检查长度不检查堆顶关系我在刷堆专题时最受益的一次是某天晚上把这三个模板各默写了两遍第二天面试“前K个高频元素”直接顺手。刷题不需要把堆题的所有变形都做完先把这三类场景的模板敲熟再去碰变种题你会发现力扣热题100里的堆题真的就是换壳不换核。如果你正卡在堆这个标签上不用慌把上面几段代码跑通再拿这张清单对照一遍多半就通了。