企业官网建设流程全解析

不止一个读者问过我：二叉树学完了，接下来是不是就该学那些花里胡哨的平衡树、红黑树了？先别急。在二叉树这条线上，有一个结构是你绕不过去、而且几乎天天在用的——堆。它披着完全二叉树的外衣，却靠数组存储吃饭；面试里TopK、堆排序、数据流中位数全是它在撑场面；STL里的priority_queue底层也是它。

这篇继续二叉树系列，把堆从定义到应用、从手写实现到STL实战一次性聊透。适合刚学完二叉树基础、准备刷题或复习数据结构的读者，也适合那些“会用priority_queue但说不清底层原理”的人补上最后一环。

1. 堆到底是棵什么树：从完全二叉树到数组存储

堆常被叫作“二叉堆”，但它和普通二叉树最大的区别在两点：结构上它必须是完全二叉树，序关系上它有堆序性。这两个性质缺一不可，而且它们直接决定了堆能用数组高效存储、能在O(log n)内完成插入和删除。

1.1 完全二叉树这个硬性要求是怎么来的

完全二叉树的定义是：除了最后一层，每一层都是满的，最后一层的节点都靠左排列。为什么堆必须长成这样？因为只有完全二叉树才能保证“用数组连续存储不浪费空间”。你想，如果中间空一个位置，数组里就得多留一个坑来标记“这里没节点”，存储效率直接打折；更重要的是，父子节点的下标关系就没那么干净了。

把这层关系写在明面上：数组下标从0开始的话，对下标为i的节点，它的左孩子是2*i + 1，右孩子是2*i + 2，父节点是(i - 1) / 2（整数除法）。这套公式是堆一切操作的基石。后面你手写堆的时候会反复用到，建议直接刻进肌肉记忆。

有的教材（包括王道数据结构）用的是从下标1开始的写法，左孩子2*i、右孩子2*i + 1、父节点i/2。两种都能用，但刷LeetCode时默认数组是0基下标，我建议统一按0基来理解和实现，避免笔试时临时换算出错。

1.2 大顶堆与小顶堆：一个关于“谁说了算”的约定

堆序性分两种：大顶堆（最大堆）要求每个节点的值都大于等于它的孩子节点，所以堆顶是最大值；小顶堆（最小堆）正好相反，堆顶是最小值。注意一个容易犯迷糊的点——堆序性只约束“父节点和孩子节点的关系”，不约束“兄弟节点之间的关系”。也就是说，左孩子和右孩子谁大谁小无所谓，它们只各自受父节点压制。

这一点和二叉搜索树形成鲜明对比。BST要求左子树所有节点都小于根、右子树都大于根，这种强约束让它能直接用来查找；堆只保证堆顶极值可O(1)访问，其他节点的相对次序是“半无序”的。所以堆不是用来“搜索”的，它是用来“快速找极值”的。

1.3 为什么堆可以用数组“假装”成树

用数组存完全二叉树时，下标天然编码了树的拓扑关系。向堆里插入一个元素，本质就是往数组末尾追加一个元素，然后让它“向上爬”到合适位置；删除堆顶，本质是拿最后一个元素补到堆顶，然后让它“向下滚”到合适位置。整个过程不需要任何指针、不需要动态分配节点，内存连续、缓存友好，这就是工程里堆能打得过链式树的重要原因。

用生活类比理解：堆就像公司里的“汇报关系图”——每个人都有且只有一个上级，但平级之间不用互相管。你只需要知道谁是你的直属上司，就能从最底层一路往上汇报到CEO。数组存储就是这个汇报关系的指针表。

2. 上滤与下滤：堆的灵魂操作

堆的插入和删除，说穿了就是两个动作：上滤（sift up）和下滤（sift down）。搞懂这两个操作，堆的核心就算拿下了。

2.1 插入元素：先塞到末尾，再往上爬

插入过程用上滤。新元素先放到数组末尾（相当于在完全二叉树最后一层最右边加一个叶子节点），然后不断和父节点比较：小顶堆里如果新元素比父节点小，就交换位置，继续向上比较；直到它不比父节点小，或者已经爬到堆顶。

// C++ 小顶堆插入，数组 v 为 0 基下标 void siftUp(vector<int>& v, int i) { while (i > 0) { int parent = (i - 1) / 2; if (v[i] < v[parent]) { swap(v[i], v[parent]); i = parent; } else { break; } } } void heapInsert(vector<int>& v, int val) { v.push_back(val); siftUp(v, v.size() - 1); }

注意这里有个很多人都忽略的细节：上滤过程中，只比较新元素和它的祖先链，不用管其他分支。因为其他分支本来就已经满足堆序性，新元素只在一条路径上冒泡，所以时间复杂度是O(log n)，而不是O(n)。

2.2 删除堆顶：用最后一个元素顶上去，再往下滚

删除堆顶的过程用下滤。先把数组最后一个元素覆盖到堆顶（相当于删掉根节点，同时让树的规模减1），然后从堆顶开始，不断和两个孩子中“更小/更大”的那一个比较：小顶堆里如果父节点比孩子大，就交换，继续向下调整，直到父节点比两个孩子都小，或者到达叶子。

// C++ 小顶堆删除堆顶，n 为元素个数 void siftDown(vector<int>& v, int i, int n) { while (true) { int l = 2 * i + 1, r = 2 * i + 2; int smallest = i; if (l < n && v[l] < v[smallest]) smallest = l; if (r < n && v[r] < v[smallest]) smallest = r; if (smallest == i) break; swap(v[i], v[smallest]); i = smallest; } } void heapPop(vector<int>& v) { if (v.empty()) return; v[0] = v.back(); v.pop_back(); if (!v.empty()) siftDown(v, 0, v.size()); }

下滤时为什么必须比较两个孩子，而不是随便挑一个？因为完全二叉树里两个孩子可能只有一个存在，而且堆序性只约束父子，两个孩子之间没有必然的大小关系。你必须先找出“更该当父节点”的那个孩子，才能保证交换后堆序性不被破坏。

2.3 一个上滤/下滤的完整追踪示例

拿小顶堆[1, 3, 5, 7, 9]举个插入例子。插入0：数组变[1, 3, 5, 7, 9, 0]，0的下标是5，父节点下标(5-1)/2=2对应值5，0<5交换，数组变[1, 3, 0, 7, 9, 5]；继续比较，0当前下标2，父节点(2-1)/2=0对应值1，0<1交换，数组变[0, 3, 1, 7, 9, 5]；下标0到顶，结束。三步搞定，全程只动了那条祖先链。

删除堆顶再追一遍：[0, 3, 1, 7, 9, 5]删堆顶，最后一个元素5覆盖到堆顶，数组变[5, 3, 1, 7, 9]；堆顶5有两个孩子3和1，1更小，5和1交换，数组变[1, 3, 5, 7, 9]；继续看5的下标2，左孩子9右孩子越界，5<9不用交换，结束。最终堆序性恢复。

这两个例子建议自己动手在纸上画一遍完全二叉树版，能明显看到“上滤”和“下滤”是沿着树的路径在做折返跑，每次只走一条路，所以对数的深度负责。

3. 建堆为什么是O(n)而不是O(n log n)：Floyd建堆法的数学直觉

很多刚学堆的人都有一个固有困惑：往空堆里逐个插入n个元素，每个都是O(log n)，那建堆明明应该是O(n log n)，怎么书上都说O(n)？

答案是：逐个插入和“一次性建堆”是两条不同的路线。前者叫“自顶向下建堆法”，复杂度确实是O(n log n)；后者叫“自底向上建堆法”（也叫Floyd建堆法），从最后一个非叶子节点开始倒着做下滤，总体复杂度是O(n)。

3.1 自底向上的操作流程

给定一个乱序数组，要原地把它调成堆：

1. 找到最后一个非叶子节点，它的下标是n/2 - 1（0基下标）。
2. 从这个节点开始，向前遍历到下标0，对每个节点执行一次siftDown。

void buildHeap(vector<int>& v) { for (int i = v.size() / 2 - 1; i >= 0; --i) { siftDown(v, i, v.size()); } }

为什么倒着做？因为siftDown的前提是“当前节点的左右子树都已经是堆”。从最后一个非叶子节点开始倒着调整，能保证处理到某个节点时，它的子树已经全部是堆了。如果从头正着做，子树还没成型，下滤就没法基于“子堆已合法”这个前提，效果会打折扣。

3.2 复杂度的直观解释：大多数节点都在底层“打短工”

你可能觉得倒着做也是每个节点O(log n)，加一起不还是O(n log n)？关键就在“高度”上——siftDown的耗时不是对每个节点都一样，它取决于节点的高度（到叶子的距离），而完全二叉树里越往下的节点数量越多、高度越小。

最后一层有n/2个叶子节点，它们根本不用做任何调整，耗时0；倒数第二层有n/4个节点，每个最多下滤1层；倒数第三层n/8个节点，每个最多下滤2层……把每层的总耗时加起来，就是：

T(n) = 0 * (n/2) + 1 * (n/4) + 2 * (n/8) + 3 * (n/16) + ... = n * (0/2 + 1/4 + 2/8 + 3/16 + ...) = n * (1) = O(n)

括号里的级数收敛到一个常数，所以整体是线性复杂度。背结论的同时建议把这个推导过程看懂，面试里被追问“为什么建堆是O(n)”时，能把上面这个求和公式写出来，就已经超过90%的候选人了。

3.3 两种建堆方式的实际差距

你可以自己跑个实验：构造100万个随机数，分别用“逐个插入”和“Floyd建堆”原地建堆，前者明显慢一个数量级。这个差距在数据量小的时候没什么感觉，但堆排序、优先队列初始化等场景下，n经常会到百万甚至千万级别，O(n log n)和O(n)的差距就非常可观了。

4. 堆排序与TopK：面试最常考的两个堆应用

堆最出圈的两个应用就是堆排序和TopK问题。这俩在算法面试里出现的频率高到离谱，而且解法高度模板化，值得单独拎出来练熟。

4.1 堆排序：建堆加反复删除堆顶

堆排序的思路一句话就能说完：建一个大顶堆，然后把堆顶最大值和末尾元素交换，堆规模减1，再对堆顶做一次下滤恢复堆序性，重复直到堆里只剩一个元素。升序排序用大顶堆，降序排序用小顶堆，这是初学者最容易记反的点——大顶堆每次把最大值放到末尾，最终数组就是升序。

void heapSort(vector<int>& v) { // 1. 建堆（大顶堆） for (int i = v.size() / 2 - 1; i >= 0; --i) { siftDownBig(v, i, v.size()); } // 2. 逐个取出堆顶 for (int i = v.size() - 1; i > 0; --i) { swap(v[0], v[i]); siftDownBig(v, 0, i); } }

注意每次交换后，参与下滤的区间要减1，因为末尾已经放的是“排好的最大值”，不能再动。堆排序时间复杂度稳定在O(n log n)，空间复杂度O(1)，但它不稳定——相等的元素排序后相对顺序可能被破坏。实际工程里排序基本还是用快排、归并，堆排序更大的价值在“异步任务调度”“带优先级的消息队列”这些需要动态维护极值的场景。

4.2 TopK问题：小顶堆存大值、大顶堆存小值

求一个数组里最大的K个数，最直觉的做法是排序取前K个，复杂度O(n log n)。用堆可以做到O(n log K)，而且不需要一次性把数据全load进内存，非常适合处理海量数据。

核心思路：维护一个大小为K的小顶堆。遍历每个元素时，如果堆还没满就塞进去；堆满了且当前元素比堆顶大，就弹出堆顶、插入当前元素。这样小顶堆里始终存的是“当前见过的最大的K个数”，堆顶就是这K个数里的最小值（即候选答案的“门槛”）。

vector<int> topK(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆 for (int x : nums) { if (pq.size() < k) { pq.push(x); } else if (x > pq.top()) { pq.pop(); pq.push(x); } } vector<int> res; while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); } return res; }

求前K小则用大顶堆，逻辑镜像对称。很多人在这一步犯迷糊：为什么“最大的K个”要用小顶堆？因为小顶堆的堆顶是堆里最小的那个，新元素只要比这个“最小门槛”大，就说明它值得被留下，同时把门槛弹出去，堆里始终是最大的K个。反向理解一下——如果换用大顶堆，堆顶是最大值，新元素进来要跟最大值比，那堆里存的就是“最大的K个”？显然是错的，大顶堆会把你引导向错误的方向。

4.3 TopK在海量数据场景下的真实价值

笔试里TopK直接用一个priority_queue就能过，但实际工程里数据量往往是TB级别，不可能全部装进内存。堆解决方案真正的优势是：它只需要维护K个元素的堆，内存占用O(K)，数据可以流式处理，每来一条数据处理一条。比如统计一个超大日志文件里出现次数最多的100个IP，你不需要把整个日志读进内存，一行一行读、一行一行更新堆，内存占用始终很小。

我个人在实习时处理过千万级的点击流数据，当时的方案就是“哈希表统计频次+小顶堆维护Top100”。整个流程非常顺，难点反而不在堆，而在哈希表的内存优化。堆这层只要写对了一次，后续基本不用再动。

5. “两个堆”思路：实时中位数问题的经典解

热搜词里有一句话特别有意思：“大顶堆放小半，小顶堆放大半，维持平衡，中位数从堆顶取。插入O(log n)”。这是数据流中位数问题的核心思路，也是堆这个结构最能体现“组合拳”威力的一道题。

5.1 为什么不能用排序做数据流中位数

题目要求是：不断有数字流入，每来一个数，都要能返回当前所有数的中位数。如果每次来一个新数就重新排序，单次复杂度O(n log n)，数据流几万条之后就扛不住了。中位数定义的天然特点是“一半小于它、一半大于它”，这正好可以和堆的“快速拿极值”特性对上——用两个堆分别维护“较小的一半”和“较大的一半”。

5.2 双堆维护的完整流程

设计思路：

• 大顶堆maxHeap存较小的一半数，堆顶是这一半里最大的；
• 小顶堆minHeap存较大的一半数，堆顶是这一半里最小的；
• 两个堆大小差不超过1，且maxHeap的堆顶 <=minHeap的堆顶。

中位数就好取了：如果总数是奇数，中位数是元素个数多的那个堆的堆顶；如果总数是偶数，中位数是两个堆顶的平均值。

插入逻辑：

1. 如果当前数 <=maxHeap的堆顶（或者maxHeap为空），插入maxHeap；否则插入minHeap。这里也可以偷懒固定策略，比如总是先插maxHeap，再用调整逻辑兜底。
2. 每插入一个数之后检查两边大小：
   • 如果maxHeap比minHeap多2个，把maxHeap堆顶移到minHeap；
   • 如果minHeap比maxHeap多2个（用固定先插maxHeap的策略通常不会出现），把minHeap堆顶移到maxHeap。

5.3 一个完整的代码骨架

class MedianFinder { private: priority_queue<int> maxHeap; // 较小的一半 priority_queue<int, vector<int>, greater<int>> minHeap; // 较大的一半 public: void addNum(int num) { // 先保证左边（小的一半）的最大值 <= 右边（大的一半）的最小值 if (maxHeap.empty() || num <= maxHeap.top()) { maxHeap.push(num); } else { minHeap.push(num); } // 平衡两边数量 if (maxHeap.size() > minHeap.size() + 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } else if (minHeap.size() > maxHeap.size() + 1) { maxHeap.push(minHeap.top()); minHeap.pop(); } } double findMedian() { if (maxHeap.size() == minHeap.size()) { return (maxHeap.top() + minHeap.top()) / 2.0; } return maxHeap.size() > minHeap.size() ? maxHeap.top() : minHeap.top(); } };

每次插入最多调整一次、移动一个元素，所以单次插入O(log n)，取中位数O(1)。这个配合在LeetCode 295（数据流的中位数）里就是标准解法，面试里考这道题基本就是在考你有没有“把一个不变量（两边平衡+左边最大值<=右边最小值）管理好”的能力。

5.4 双堆思想的延展

两个堆的“一分为二”思路还能解很多问题，比如求滑动窗口中的中位数（再加一个延迟删除的机制），或者最大/最小K个数的动态维护。核心思想都是“用大顶堆管较小部分的关键极值，用小顶堆管较大部分的关键极值，用堆顶搭一座桥，通过桥来汇总答案”。面试时想秀操作，可以在写完基本解法后主动提一句“这个思路还能扩展到XX场景”，比闷头敲代码加分得多。

6. 实战避坑：手写堆与priority_queue使用细节

理论说再多，落地的时候该踩的坑一个都不会少。下面这些细节全部来自我刷题和写工程代码时的真实教训，按重要程度排个序。

6.1priority_queue默认是大顶堆，小顶堆要写完整模板参数

C++的priority_queue<T>默认是priority_queue<T, vector<T>, less<T>>，也就是大顶堆。要小顶堆必须写priority_queue<int, vector<int>, greater<int>>。两个模板参数一个不能少，少了编译不过或者行为不对。

Java的PriorityQueue默认是小顶堆，和C++正好相反，跨语言刷题时千万注意。我见过不少C++选手切到Java后习惯性认为pq.peek()是最大值，结果在需要最大值的地方取出了最小值，debug到怀疑人生。

6.2 自定义比较器最容易出隐性问题

按结构体的某个字段排序时，很多人会直接写lambda，但C++的priority_queue和sort的比较器语义是反的——sort里返回true表示“a排前面”，priority_queue里返回true表示“a的优先级低、会被沉到底部”。

struct Node { int cost; }; struct Cmp { bool operator()(const Node& a, const Node& b) const { return a.cost > b.cost; // 注意：这是小顶堆语义 } }; priority_queue<Node, vector<Node>, Cmp> pq;

如果不清楚这个语义，写出的堆可能和你预期的完全反着。我的建议是：自定义比较器时先用三个元素做一遍打印测试，确认堆顶是你想要的那个极值，再往下写业务逻辑。

6.3 手写堆时的边界条件清单

手写堆用于笔试时，边界条件漏一个就是WA或者越界。列一份我踩过坑的检查清单：

• siftDown里孩子下标判断：l < n和r < n，不能写成<=，否则数组越界；
• 空堆和单元素堆：插入、删除、取堆顶三种操作都要单独考虑；
• 删除堆顶用末尾元素覆盖后，如果堆只剩一个元素不需要下滤；
• 上滤的下标更新是i = (i - 1) / 2，别写成i /= 2（0基下标下这不是父节点公式）；
• 建堆的循环起点是n/2 - 1，经常有人写成n/2甚至n-1——多调几个叶子节点问题不大，但会浪费无谓的比较。

6.4 工程上堆的内存分布与性能特征

数组存储的堆天然缓存友好，因为父子节点在内存里挨得很近。但也要注意一点：priority_queue底层是vector，插入时如果容量不够会触发整体扩容，把旧数据拷贝到新内存。如果提前知道数据规模，可以用vector::reserve预留空间，避免反复扩容。这个优化在单次插入里看不出什么，但在千万级数据的建堆场景下能省下不少耗时。

6.5 STL堆算法：你不知道的make_heap全家桶

除了priority_queue，C++的<algorithm>里还有一套直接用迭代器操作的堆算法：make_heap、push_heap、pop_heap、sort_heap。它们比priority_queue更灵活，因为你可以直接访问堆里的所有元素，而不只是堆顶。

• make_heap(v.begin(), v.end())：原地建堆，默认大顶堆；
• push_heap(v.begin(), v.end())：把最后一个元素插入堆，使用前必须先把元素push_back进去；
• pop_heap(v.begin(), v.end())：把堆顶换到末尾，然后调整堆，使用后元素还在v里，需要pop_back弹出；
• sort_heap(v.begin(), v.end())：对堆进行排序，即堆排序的原地版本。

这套接口在某些需要“既能当堆用、又能随时遍历全部元素”的场景下很好使，比如Dijkstra算法的优先队列优化，如果你需要更新堆中某元素的优先级，priority_queue做不到，用make_heap这套就可以自己维护索引，找到元素位置再调整。

写在最后

堆这个结构，代码量不大，但思想密度很高。学完二叉树再学堆，你会明显感觉到“树的形态”和“数组的存储”两者的结合有多巧妙——树负责提供逻辑上的层次关系，数组负责提供物理上的连续存储，两者各取所长。

如果你正在刷题，我建议你亲手把buildHeap、siftUp、siftDown、heapSort和双堆中位数这五段代码各写三遍：第一遍照着敲，第二遍默写，第三遍调试通过。三遍之后，堆相关的高频题基本都能做到信手拈来。这个练习过程里踩到的每一个越界、每一个死循环，都会变成你面试时最真实的谈资。