企业官网建设流程全解析

力扣热题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*i+1，右孩子是2*i+2，父节点是(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用heapq，Java用PriorityQueue，两者的默认行为、常见技巧和坑不太一样。

4.1 Python的heapq

heapq默认是最小堆，核心方法就几个：

• 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的PriorityQueue

Java的PriorityQueue默认是最小堆，可以这样创建：

// 默认最小堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 最大堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 自定义比较器，按字符串长度 PriorityQueue<String> byLength = new PriorityQueue<>((a, b) -> a.length() - b.length());

核心方法对应关系：

Java的PriorityQueue有三个坑要特别注意：

• 迭代顺序不保证有序，只有poll()时才保证从小到大依次弹出。
• 自定义对象必须提供Comparator，否则直接入堆会抛ClassCastException。
• remove(Object)的复杂度是O(N)，不是O(logN)，如果需要在堆中删除非堆顶元素，要考虑懒删除。

4.3 Python和Java的对比

单说刷题，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个高频元素”直接顺手。刷题不需要把堆题的所有变形都做完，先把这三类场景的模板敲熟，再去碰变种题，你会发现力扣热题100里的堆题，真的就是换壳不换核。如果你正卡在堆这个标签上，不用慌，把上面几段代码跑通，再拿这张清单对照一遍，多半就通了。