1. 从“堆”这个字说起它到底是什么每次听到“堆”这个字很多刚接触数据结构的同学脑子里可能先蹦出来的是“内存堆”或者“一堆东西”。但在数据结构与算法的世界里“堆”是一个特指它是一种非常特殊且高效的完全二叉树。我刚开始学的时候也犯过迷糊后来才明白它的“堆”更像是一个有严格家规的大家族而不是随便堆放杂物的仓库。这个家族的规矩很简单但很有效对于“大根堆”来说家族里的“族长”根节点必须是辈分最高、数值最大的而且这个规矩不仅适用于族长家族里的每一个“小家庭”子树都必须遵守——任何一个父亲节点的值都必须大于或等于它的两个儿子节点的值。反过来“小根堆”就是另一个极端族长最小每个父亲都比儿子小。这个看似简单的规则却让堆在解决“快速找最值”这类问题上展现出了惊人的效率其核心操作的时间复杂度都能控制在 O(log n) 的级别。为什么我们要大费周章地学习堆的构建、插入、删除和排序呢因为它在实际应用中无处不在。当你玩王者荣耀系统需要实时从千万玩家中找出当前分数最高的几位进行“国服最强”排名时背后很可能就是一个大根堆在高效工作当你的电脑操作系统需要管理众多优先级不同的任务时小根堆就是调度器的核心组件之一再比如我们熟知的堆排序算法以及构成许多高级算法如Dijkstra最短路径、Huffman编码基石——优先级队列其底层实现都离不开堆。理解堆就是握住了打开高效算法世界的一把关键钥匙。接下来我就结合代码把这把钥匙的每一个齿牙都给你讲明白。2. 堆的基石如何用数组表示一棵完全二叉树在动手写代码之前我们必须先建立一种极其重要的心智模型堆在逻辑上是一棵完全二叉树但在物理存储上它通常用一个一维数组来实现。这是理解所有堆操作的基础也是其高效的原因。为什么可以用数组这得益于完全二叉树的完美特性。对于一棵完全二叉树如果按照从上到下、从左到右的顺序给每个节点编号从0开始或从1开始那么每个节点的父子关系可以通过简单的算术计算得到无需像链表那样存储复杂的指针。我们以数组下标从0开始为例这也是C、Java等语言中的常见方式来看看这个神奇的映射关系对于一个下标为i的节点它的左孩子的下标是leftChild(i) 2 * i 1它的右孩子的下标是rightChild(i) 2 * i 2它的父亲的下标是parent(i) (i - 1) / 2这里利用整数除法向下取整的特性例如数组[50, 30, 20, 15, 10, 8]在逻辑上对应的就是一棵完全二叉树根节点50在arr[0]它的左孩子30在arr[1]右孩子20在arr[2]以此类推。注意有些教材或代码实现为了方便计算会选择让数组下标从1开始此时父子节点的计算公式会略有不同left2*i,right2*i1,parenti/2。两种方式本质一样本文后续代码将统一采用下标从0开始的约定因为这与大多数编程语言的原生数组特性一致。这种表示法的巨大优势在于节省空间不需要存储左右子节点的指针仅用连续内存存储数据本身。缓存友好数组元素在内存中连续存储CPU缓存命中率高访问速度快。快速定位通过O(1)复杂度的计算即可找到任意节点的父节点或子节点这是后续所有高效操作的前提。理解了这一点我们就把一棵树“拍扁”成了一个数组所有对堆的操作都可以转化为在这个数组上进行特定规则的“元素交换”。3. 维护堆秩序的核心算法上浮与下沉堆的所有操作无论是插入新元素还是删除根节点其核心目标都是在操作后恢复堆的性质。实现这一目标依赖于两个最基础、最核心的内部方法上浮Sift Up和下沉Sift Down 也常被称为堆化 Heapify。可以说吃透了这两个函数堆的所有秘密就掌握了八成。3.1 上浮让新来的“刺头”找到自己的位置想象一下你的团队大根堆本来秩序井然老大最大。突然空降了一个能力很强值很大的新人如果随便把他放在末尾就破坏了“领导必须比下属强”的规矩。怎么办我们需要让他和自己的直接上级比如果比上级强就交换位置然后再和新的上级比直到他不再比上级强或者他已经成了老大。这个过程就是“上浮”。上浮Sift Up通常发生在向堆中插入新元素之后。新元素被放在数组末尾即完全二叉树的最后一个叶子节点位置它可能会破坏堆的性质。上浮操作就是让这个新节点沿着通往根节点的路径向上“攀爬”不断与它的父节点比较如果它比父节点大对于大根堆就交换它们的位置直到它不大于其父节点或者到达了根节点。代码实现大根堆// 将索引为 i 的节点进行上浮操作 void siftUp(vectorint heap, int i) { while (i 0) { int parent (i - 1) / 2; // 计算父节点索引 if (heap[i] heap[parent]) { break; // 当前节点已经不大于父节点堆性质满足停止上浮 } swap(heap[i], heap[parent]); // 否则交换当前节点“升职” i parent; // 更新当前节点索引为父节点位置继续向上比较 } }为什么是 O(log n)因为完全二叉树的高度是 log₂(n)n为节点数上浮操作最多就是从叶子节点走到根节点所以时间复杂度是 O(log n)。3.2 下沉让“德不配位”的领导下来另一种情况团队的老大根节点因为某些原因比如被调走/删除离开了我们让原本在末尾的一个普通成员临时顶替老大的位置。显然他很可能无法服众值不是最大的。为了恢复秩序我们需要让这个临时老大和他的两个直接下属比选出能力最强的那个下属如果下属比他还强就交换位置让他“下沉”一级。然后他在新的岗位上继续和新的下属比直到他比所有下属都强或者他已经成了基层员工叶子节点。这个过程就是“下沉”。下沉Sift Down通常发生在删除堆顶元素或构建堆的过程中。当我们移除堆顶最大值后通常会把数组最后一个元素移到堆顶。这个“外来户”几乎肯定会破坏堆的性质。下沉操作就是让这个新堆顶节点沿着树向下“沉降”不断与它的左右孩子中较大的那个比较对于大根堆如果它小于那个较大的孩子就交换它们的位置直到它不小于它的所有孩子或者到达了叶子节点。代码实现大根堆// 将索引为 i 的节点进行下沉操作n 是当前堆的大小 void siftDown(vectorint heap, int n, int i) { int largest i; // 先假设当前节点是最大的 int left 2 * i 1; int right 2 * i 2; // 与左孩子比较 if (left n heap[left] heap[largest]) { largest left; } // 与右孩子比较 if (right n heap[right] heap[largest]) { largest right; } // 如果最大的不是自己说明需要下沉 if (largest ! i) { swap(heap[i], heap[largest]); siftDown(heap, n, largest); // 递归地在新的位置上继续下沉 } } // 也可以使用循环非递归实现 void siftDownIterative(vectorint heap, int n, int i) { while (true) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n heap[l] heap[largest]) largest l; if (r n heap[r] heap[largest]) largest r; if (largest i) break; // 当前节点已经比孩子都大停止下沉 swap(heap[i], heap[largest]); i largest; // 更新当前节点索引继续下一轮比较 } }为什么也是 O(log n)同样的道理下沉操作最多就是从根节点走到叶子节点路径长度同样是树的高度即 O(log n)。实操心得在具体实现时siftDown的递归版本代码简洁但存在递归栈开销。在性能要求极高的场景如排序、高频交易我通常会使用循环的非递归版本。而对于siftUp因为路径通常更短新插入节点往往在底层递归或循环的差异不大可根据个人喜好选择。掌握了“上浮”和“下沉”我们就有了维护堆秩序的全部工具。接下来所有对外暴露的堆操作都只是组合运用这两个工具而已。4. 堆的四大基本操作构建、插入、删除与取顶现在我们利用“上浮”和“下沉”这两个核心工具来实现堆的四个基本操作。我会给出完整的代码片段并解释每一个步骤的意图。4.1 堆的构建如何将一个无序数组变成堆给你一个乱序的数组如何高效地将其调整成一个符合堆结构的数组一个直观但低效的想法是新建一个空堆然后遍历数组对每个元素调用插入操作即siftUp。这种方法的时间复杂度是 O(n log n)。但有一个更聪明、复杂度为O(n)的方法“从最后一个非叶子节点开始向前逐个进行下沉操作”。为什么是最后一个非叶子节点因为叶子节点没有孩子它们本身已经是一个合法的堆单节点。最后一个非叶子节点的下标就是最后一个节点的父节点parent(n-1)。为什么复杂度是 O(n)这是一个精妙的数学结论。直观上大部分需要下沉的节点都在树的底层它们需要下沉的深度很浅。详细推导涉及级数求和结论是整体操作次数与 n 成线性关系。代码实现大根堆构建// 将无序数组 arr 在原地构建成一个大根堆 void buildMaxHeap(vectorint arr) { int n arr.size(); // 从最后一个非叶子节点开始向前遍历到根节点 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, n, i); } }示例将[3, 5, 1, 7, 2, 8, 4]构建成大根堆。n7, 最后一个非叶子节点下标i 7/2 -1 2(值为1)。对i2下沉比较1和它的孩子4交换数组变为[3,5,4,7,2,8,1]。i1(值为5)比较5和它的孩子(7,2)7更大交换5和7数组变为[3,7,4,5,2,8,1]。交换后5在新位置(i3)需要继续下沉吗它的孩子是151停止。i0(值为3)比较3和它的孩子(7,4)7更大交换3和7数组变为[7,3,4,5,2,8,1]。交换后3在新位置(i1)需要继续下沉比较3和它的孩子(5,2)5更大交换3和5数组变为[7,5,4,3,2,8,1]。交换后3在新位置(i3)无需再下沉。最终得到大根堆[7,5,8,3,2,1,4]注意8在第二层它比父节点5大所以上浮到了正确位置这是在后续的下沉中完成的。4.2 插入操作向堆中添加新元素插入操作遵循一个固定流程将新元素追加到数组末尾然后对其执行上浮操作。void heapInsert(vectorint heap, int value) { heap.push_back(value); // 1. 放到末尾 siftUp(heap, heap.size() - 1); // 2. 上浮 }时间复杂度O(log n)。因为一次push_back是 O(1)平均分摊一次siftUp是 O(log n)。4.3 删除堆顶弹出操作移除并返回最大/最小值这是堆的另一个关键操作比如从优先级队列中取出最高优先级的任务。步骤是取出堆顶元素通常是arr[0]作为返回值。将堆的最后一个元素移动到堆顶arr[0] arr.back()。从堆中移除最后一个元素arr.pop_back()。对新的堆顶元素执行下沉操作以恢复堆的性质。int heapPop(vectorint heap) { if (heap.empty()) { // 根据实际情况抛出异常或返回特定值 throw runtime_error(Heap is empty); } int maxValue heap[0]; // 1. 保存堆顶值 heap[0] heap.back(); // 2. 末尾元素移到堆顶 heap.pop_back(); // 3. 删除末尾元素 if (!heap.empty()) { siftDown(heap, heap.size(), 0); // 4. 新的堆顶下沉 } return maxValue; }时间复杂度O(log n)。一次交换是 O(1)一次siftDown是 O(log n)。4.4 查看堆顶取最值这是最简单的操作直接返回数组第一个元素即可时间复杂度 O(1)。int heapPeek(const vectorint heap) { if (heap.empty()) { throw runtime_error(Heap is empty); } return heap[0]; }5. 堆排序一种原地、不稳定的O(n log n)排序堆排序是堆数据结构最经典的应用之一。它巧妙地利用了堆的特性实现了原地排序除了递归栈或循环变量几乎不需要额外空间且时间复杂度稳定在 O(n log n)。堆排序的算法思想建堆将待排序的数组原地构建成一个大根堆。此时最大的元素位于arr[0]。交换与收缩将堆顶元素arr[0]当前最大值与堆的最后一个元素arr[n-1]交换。这样最大值就被放置在了它最终的正确位置数组末尾。堆大小减1此时除了最后一个元素数组的前n-1个元素可能不再满足堆的性质。但重要的是新的堆顶元素原最后一个元素通常很小。我们对新的堆顶元素索引0在缩小后的堆大小为 n-1中进行下沉操作siftDown(arr, n-1, 0)使其重新成为一个有效的大根堆。重复重复步骤2和3每次将堆的大小减1直到堆的大小为1。此时数组已经完全有序。关键点每次交换后最大值被移到当前未排序部分的末尾并且通过一次下沉操作我们能在 O(log n) 时间内重新找到剩余元素中的最大值。代码实现void heapSort(vectorint arr) { int n arr.size(); // 1. 构建初始大根堆 buildMaxHeap(arr); // 时间复杂度 O(n) // 2. 逐个提取元素 for (int i n - 1; i 0; i--) { // 将当前堆顶最大值与末尾元素交换 swap(arr[0], arr[i]); // 堆的大小减1并对新的堆顶进行下沉恢复堆性质 siftDown(arr, i, 0); // 注意这里堆的大小是 i不是 n } // 循环结束后arr[0] 是当前堆大小为1的堆顶也是全局最小值数组整体升序排列 }时间复杂度分析建堆O(n)总共进行 n-1 次交换和下沉操作每次下沉 O(log n)所以总的是 O(n log n)。整体复杂度为 O(n n log n) O(n log n)。空间复杂度O(1)原地排序。稳定性堆排序是不稳定的排序算法。因为在交换堆顶和末尾元素时可能会改变相同关键字的原始相对顺序。例如对[5a, 5b, 3]用a,b区分相同值建堆后第一次交换就可能破坏5a和5b的顺序。实操心得与对比堆排序在平均和最坏情况下都是 O(n log n)这点比快速排序最坏 O(n²)好但通常其常数因子比快速排序大所以实际运行速度往往不如优化过的快排。然而堆排序的亮点在于原地和最坏情况有保障。在内存紧张或对最坏运行时间有严格要求的场景下堆排序是一个可靠的选择。另外堆排序的交换次数相对较多。6. 小根堆原理相同规则相反理解了所有的大根堆操作小根堆就易如反掌了。小根堆的定义是每个节点的值都小于或等于其子节点的值。因此堆顶元素是整个堆中的最小值。如何将大根堆代码改为小根堆非常简单只需要在所有比较大小的逻辑上取反即可。siftUp将比较条件从heap[i] heap[parent]改为heap[i] heap[parent]。siftDown在寻找largest的地方改为寻找smallest并将比较条件从改为。buildMinHeap,heapInsert,heapPop等函数内部调用相应的siftUp或siftDown即可。小根堆的应用场景构建优先级队列获取最小优先级任务如 Dijkstra 算法中需要频繁提取当前距离最小的节点。求数据流中的 Top K 小元素维护一个大小为 K 的小根堆堆顶就是第 K 小的元素当新元素比堆顶大时就替换堆顶并下沉。哈夫曼编码需要反复合并频率最小的两个节点。7. 避坑指南与性能优化实战理论懂了代码写了但在实际项目中使用堆时还是会遇到一些坑。这里分享几个我踩过的雷和优化技巧。7.1 索引计算与边界检查这是最容易出 bug 的地方之一。务必确保在计算左右孩子索引 (2*i1,2*i2) 和父节点索引 ((i-1)/2) 时i的值是有效的。特别是在siftDown循环中判断left n和right n至关重要否则会数组越界。// 错误的示例忘记检查 left 和 right 是否越界 void siftDownBad(vectorint heap, int n, int i) { while (true) { int l 2 * i 1; int r 2 * i 2; int largest i; // 如果 l 或 r 大于等于 n下面的 heap[l] 访问就是非法的 if (heap[l] heap[largest]) largest l; if (heap[r] heap[largest]) largest r; // ... } }7.2 理解“原地”与“非原地”操作堆排序是“原地”的因为它直接在输入数组上操作。但很多情况下我们可能需要一个独立的堆数据结构。这时通常内部维护一个动态数组如 C 的vector Java 的ArrayList。在插入时动态扩容在删除时可能缩容。要了解你所使用语言中动态数组扩容的成本通常是均摊 O(1)但在对性能极其敏感的场景如果知道数据量上限可以提前reserve空间以避免多次扩容。7.3 自定义比较器与复杂数据类型实际应用中堆里存的往往不是简单的整数而是对象、结构体或键值对。例如在任务调度中堆里存的是(优先级, 任务ID)。这时我们需要定义如何比较这些元素。在 C 中可以通过重载运算符或为priority_queue提供自定义比较仿函数。在 Java 中可以为PriorityQueue提供Comparator。// C 示例存储 pair优先级, 任务ID希望按优先级最小堆 struct Task { int priority; int id; // 重载 运算符定义“小于”即优先级更高值更小 bool operator(const Task other) const { // 对于最小堆我们希望优先级数字小的在堆顶 // 但标准库的 priority_queue 默认是最大堆所以这里需要反向逻辑 // 更常见的做法是使用自定义比较器 return priority other.priority; // 注意这是为了适配默认最大堆的 trick } }; // 更清晰的做法使用自定义比较器 auto cmp [](const Task a, const Task b) { return a.priority b.priority; }; priority_queueTask, vectorTask, decltype(cmp) minHeap(cmp);注意C STL 的priority_queue默认是最大堆使用lessT其“顶”元素是最大的。如果你想实现最小堆需要提供greaterT或自定义返回a b的比较器。这是一个常见的混淆点。7.4 堆并非银弹选择合适的数据结构堆的强项是快速访问和删除最值O(1) 和 O(log n)。但它不擅长查找任意元素需要 O(n) 遍历。删除任意非堆顶元素需要先 O(n) 找到删除后还需要 O(log n) 调整。合并两个堆朴素合并是 O(n log n)有更高效的“可合并堆”如左倾堆、二项堆、斐波那契堆但实现复杂。如果你的场景需要频繁的任意查找或删除可能需要结合哈希表实现一个“索引堆”或考虑其他数据结构如平衡二叉搜索树。7.5 从“小土堆”到工业级实现网上很多教程包括一些热门的“小土堆”入门笔记为了简化实现的堆可能没有考虑异常处理、模板化、迭代器安全性等问题。在实际工程中一个健壮的堆实现应该模板化支持任意可比较数据类型。异常安全在pop空堆、peek空堆时有明确行为抛异常或返回特定值。提供迭代器如果需要但要注意堆的迭代器遍历顺序并不代表排序顺序。封装性将内部数组和核心方法siftUp/siftDown设为私有只暴露push,pop,top,size,empty等公共接口。最后再强调一次堆的思想是优美的其核心——siftUp和siftDown——是理解所有高级堆变种和优先级队列应用的基础。无论是解决 Top K 问题还是实现高效的调度算法当你意识到问题核心是“动态维护一个最值集合”时堆就应该成为你工具箱里的首选之一。
1. 从“堆”这个字说起它到底是什么每次听到“堆”这个字很多刚接触数据结构的同学脑子里可能先蹦出来的是“内存堆”或者“一堆东西”。但在数据结构与算法的世界里“堆”是一个特指它是一种非常特殊且高效的完全二叉树。我刚开始学的时候也犯过迷糊后来才明白它的“堆”更像是一个有严格家规的大家族而不是随便堆放杂物的仓库。这个家族的规矩很简单但很有效对于“大根堆”来说家族里的“族长”根节点必须是辈分最高、数值最大的而且这个规矩不仅适用于族长家族里的每一个“小家庭”子树都必须遵守——任何一个父亲节点的值都必须大于或等于它的两个儿子节点的值。反过来“小根堆”就是另一个极端族长最小每个父亲都比儿子小。这个看似简单的规则却让堆在解决“快速找最值”这类问题上展现出了惊人的效率其核心操作的时间复杂度都能控制在 O(log n) 的级别。为什么我们要大费周章地学习堆的构建、插入、删除和排序呢因为它在实际应用中无处不在。当你玩王者荣耀系统需要实时从千万玩家中找出当前分数最高的几位进行“国服最强”排名时背后很可能就是一个大根堆在高效工作当你的电脑操作系统需要管理众多优先级不同的任务时小根堆就是调度器的核心组件之一再比如我们熟知的堆排序算法以及构成许多高级算法如Dijkstra最短路径、Huffman编码基石——优先级队列其底层实现都离不开堆。理解堆就是握住了打开高效算法世界的一把关键钥匙。接下来我就结合代码把这把钥匙的每一个齿牙都给你讲明白。2. 堆的基石如何用数组表示一棵完全二叉树在动手写代码之前我们必须先建立一种极其重要的心智模型堆在逻辑上是一棵完全二叉树但在物理存储上它通常用一个一维数组来实现。这是理解所有堆操作的基础也是其高效的原因。为什么可以用数组这得益于完全二叉树的完美特性。对于一棵完全二叉树如果按照从上到下、从左到右的顺序给每个节点编号从0开始或从1开始那么每个节点的父子关系可以通过简单的算术计算得到无需像链表那样存储复杂的指针。我们以数组下标从0开始为例这也是C、Java等语言中的常见方式来看看这个神奇的映射关系对于一个下标为i的节点它的左孩子的下标是leftChild(i) 2 * i 1它的右孩子的下标是rightChild(i) 2 * i 2它的父亲的下标是parent(i) (i - 1) / 2这里利用整数除法向下取整的特性例如数组[50, 30, 20, 15, 10, 8]在逻辑上对应的就是一棵完全二叉树根节点50在arr[0]它的左孩子30在arr[1]右孩子20在arr[2]以此类推。注意有些教材或代码实现为了方便计算会选择让数组下标从1开始此时父子节点的计算公式会略有不同left2*i,right2*i1,parenti/2。两种方式本质一样本文后续代码将统一采用下标从0开始的约定因为这与大多数编程语言的原生数组特性一致。这种表示法的巨大优势在于节省空间不需要存储左右子节点的指针仅用连续内存存储数据本身。缓存友好数组元素在内存中连续存储CPU缓存命中率高访问速度快。快速定位通过O(1)复杂度的计算即可找到任意节点的父节点或子节点这是后续所有高效操作的前提。理解了这一点我们就把一棵树“拍扁”成了一个数组所有对堆的操作都可以转化为在这个数组上进行特定规则的“元素交换”。3. 维护堆秩序的核心算法上浮与下沉堆的所有操作无论是插入新元素还是删除根节点其核心目标都是在操作后恢复堆的性质。实现这一目标依赖于两个最基础、最核心的内部方法上浮Sift Up和下沉Sift Down 也常被称为堆化 Heapify。可以说吃透了这两个函数堆的所有秘密就掌握了八成。3.1 上浮让新来的“刺头”找到自己的位置想象一下你的团队大根堆本来秩序井然老大最大。突然空降了一个能力很强值很大的新人如果随便把他放在末尾就破坏了“领导必须比下属强”的规矩。怎么办我们需要让他和自己的直接上级比如果比上级强就交换位置然后再和新的上级比直到他不再比上级强或者他已经成了老大。这个过程就是“上浮”。上浮Sift Up通常发生在向堆中插入新元素之后。新元素被放在数组末尾即完全二叉树的最后一个叶子节点位置它可能会破坏堆的性质。上浮操作就是让这个新节点沿着通往根节点的路径向上“攀爬”不断与它的父节点比较如果它比父节点大对于大根堆就交换它们的位置直到它不大于其父节点或者到达了根节点。代码实现大根堆// 将索引为 i 的节点进行上浮操作 void siftUp(vectorint heap, int i) { while (i 0) { int parent (i - 1) / 2; // 计算父节点索引 if (heap[i] heap[parent]) { break; // 当前节点已经不大于父节点堆性质满足停止上浮 } swap(heap[i], heap[parent]); // 否则交换当前节点“升职” i parent; // 更新当前节点索引为父节点位置继续向上比较 } }为什么是 O(log n)因为完全二叉树的高度是 log₂(n)n为节点数上浮操作最多就是从叶子节点走到根节点所以时间复杂度是 O(log n)。3.2 下沉让“德不配位”的领导下来另一种情况团队的老大根节点因为某些原因比如被调走/删除离开了我们让原本在末尾的一个普通成员临时顶替老大的位置。显然他很可能无法服众值不是最大的。为了恢复秩序我们需要让这个临时老大和他的两个直接下属比选出能力最强的那个下属如果下属比他还强就交换位置让他“下沉”一级。然后他在新的岗位上继续和新的下属比直到他比所有下属都强或者他已经成了基层员工叶子节点。这个过程就是“下沉”。下沉Sift Down通常发生在删除堆顶元素或构建堆的过程中。当我们移除堆顶最大值后通常会把数组最后一个元素移到堆顶。这个“外来户”几乎肯定会破坏堆的性质。下沉操作就是让这个新堆顶节点沿着树向下“沉降”不断与它的左右孩子中较大的那个比较对于大根堆如果它小于那个较大的孩子就交换它们的位置直到它不小于它的所有孩子或者到达了叶子节点。代码实现大根堆// 将索引为 i 的节点进行下沉操作n 是当前堆的大小 void siftDown(vectorint heap, int n, int i) { int largest i; // 先假设当前节点是最大的 int left 2 * i 1; int right 2 * i 2; // 与左孩子比较 if (left n heap[left] heap[largest]) { largest left; } // 与右孩子比较 if (right n heap[right] heap[largest]) { largest right; } // 如果最大的不是自己说明需要下沉 if (largest ! i) { swap(heap[i], heap[largest]); siftDown(heap, n, largest); // 递归地在新的位置上继续下沉 } } // 也可以使用循环非递归实现 void siftDownIterative(vectorint heap, int n, int i) { while (true) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n heap[l] heap[largest]) largest l; if (r n heap[r] heap[largest]) largest r; if (largest i) break; // 当前节点已经比孩子都大停止下沉 swap(heap[i], heap[largest]); i largest; // 更新当前节点索引继续下一轮比较 } }为什么也是 O(log n)同样的道理下沉操作最多就是从根节点走到叶子节点路径长度同样是树的高度即 O(log n)。实操心得在具体实现时siftDown的递归版本代码简洁但存在递归栈开销。在性能要求极高的场景如排序、高频交易我通常会使用循环的非递归版本。而对于siftUp因为路径通常更短新插入节点往往在底层递归或循环的差异不大可根据个人喜好选择。掌握了“上浮”和“下沉”我们就有了维护堆秩序的全部工具。接下来所有对外暴露的堆操作都只是组合运用这两个工具而已。4. 堆的四大基本操作构建、插入、删除与取顶现在我们利用“上浮”和“下沉”这两个核心工具来实现堆的四个基本操作。我会给出完整的代码片段并解释每一个步骤的意图。4.1 堆的构建如何将一个无序数组变成堆给你一个乱序的数组如何高效地将其调整成一个符合堆结构的数组一个直观但低效的想法是新建一个空堆然后遍历数组对每个元素调用插入操作即siftUp。这种方法的时间复杂度是 O(n log n)。但有一个更聪明、复杂度为O(n)的方法“从最后一个非叶子节点开始向前逐个进行下沉操作”。为什么是最后一个非叶子节点因为叶子节点没有孩子它们本身已经是一个合法的堆单节点。最后一个非叶子节点的下标就是最后一个节点的父节点parent(n-1)。为什么复杂度是 O(n)这是一个精妙的数学结论。直观上大部分需要下沉的节点都在树的底层它们需要下沉的深度很浅。详细推导涉及级数求和结论是整体操作次数与 n 成线性关系。代码实现大根堆构建// 将无序数组 arr 在原地构建成一个大根堆 void buildMaxHeap(vectorint arr) { int n arr.size(); // 从最后一个非叶子节点开始向前遍历到根节点 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, n, i); } }示例将[3, 5, 1, 7, 2, 8, 4]构建成大根堆。n7, 最后一个非叶子节点下标i 7/2 -1 2(值为1)。对i2下沉比较1和它的孩子4交换数组变为[3,5,4,7,2,8,1]。i1(值为5)比较5和它的孩子(7,2)7更大交换5和7数组变为[3,7,4,5,2,8,1]。交换后5在新位置(i3)需要继续下沉吗它的孩子是151停止。i0(值为3)比较3和它的孩子(7,4)7更大交换3和7数组变为[7,3,4,5,2,8,1]。交换后3在新位置(i1)需要继续下沉比较3和它的孩子(5,2)5更大交换3和5数组变为[7,5,4,3,2,8,1]。交换后3在新位置(i3)无需再下沉。最终得到大根堆[7,5,8,3,2,1,4]注意8在第二层它比父节点5大所以上浮到了正确位置这是在后续的下沉中完成的。4.2 插入操作向堆中添加新元素插入操作遵循一个固定流程将新元素追加到数组末尾然后对其执行上浮操作。void heapInsert(vectorint heap, int value) { heap.push_back(value); // 1. 放到末尾 siftUp(heap, heap.size() - 1); // 2. 上浮 }时间复杂度O(log n)。因为一次push_back是 O(1)平均分摊一次siftUp是 O(log n)。4.3 删除堆顶弹出操作移除并返回最大/最小值这是堆的另一个关键操作比如从优先级队列中取出最高优先级的任务。步骤是取出堆顶元素通常是arr[0]作为返回值。将堆的最后一个元素移动到堆顶arr[0] arr.back()。从堆中移除最后一个元素arr.pop_back()。对新的堆顶元素执行下沉操作以恢复堆的性质。int heapPop(vectorint heap) { if (heap.empty()) { // 根据实际情况抛出异常或返回特定值 throw runtime_error(Heap is empty); } int maxValue heap[0]; // 1. 保存堆顶值 heap[0] heap.back(); // 2. 末尾元素移到堆顶 heap.pop_back(); // 3. 删除末尾元素 if (!heap.empty()) { siftDown(heap, heap.size(), 0); // 4. 新的堆顶下沉 } return maxValue; }时间复杂度O(log n)。一次交换是 O(1)一次siftDown是 O(log n)。4.4 查看堆顶取最值这是最简单的操作直接返回数组第一个元素即可时间复杂度 O(1)。int heapPeek(const vectorint heap) { if (heap.empty()) { throw runtime_error(Heap is empty); } return heap[0]; }5. 堆排序一种原地、不稳定的O(n log n)排序堆排序是堆数据结构最经典的应用之一。它巧妙地利用了堆的特性实现了原地排序除了递归栈或循环变量几乎不需要额外空间且时间复杂度稳定在 O(n log n)。堆排序的算法思想建堆将待排序的数组原地构建成一个大根堆。此时最大的元素位于arr[0]。交换与收缩将堆顶元素arr[0]当前最大值与堆的最后一个元素arr[n-1]交换。这样最大值就被放置在了它最终的正确位置数组末尾。堆大小减1此时除了最后一个元素数组的前n-1个元素可能不再满足堆的性质。但重要的是新的堆顶元素原最后一个元素通常很小。我们对新的堆顶元素索引0在缩小后的堆大小为 n-1中进行下沉操作siftDown(arr, n-1, 0)使其重新成为一个有效的大根堆。重复重复步骤2和3每次将堆的大小减1直到堆的大小为1。此时数组已经完全有序。关键点每次交换后最大值被移到当前未排序部分的末尾并且通过一次下沉操作我们能在 O(log n) 时间内重新找到剩余元素中的最大值。代码实现void heapSort(vectorint arr) { int n arr.size(); // 1. 构建初始大根堆 buildMaxHeap(arr); // 时间复杂度 O(n) // 2. 逐个提取元素 for (int i n - 1; i 0; i--) { // 将当前堆顶最大值与末尾元素交换 swap(arr[0], arr[i]); // 堆的大小减1并对新的堆顶进行下沉恢复堆性质 siftDown(arr, i, 0); // 注意这里堆的大小是 i不是 n } // 循环结束后arr[0] 是当前堆大小为1的堆顶也是全局最小值数组整体升序排列 }时间复杂度分析建堆O(n)总共进行 n-1 次交换和下沉操作每次下沉 O(log n)所以总的是 O(n log n)。整体复杂度为 O(n n log n) O(n log n)。空间复杂度O(1)原地排序。稳定性堆排序是不稳定的排序算法。因为在交换堆顶和末尾元素时可能会改变相同关键字的原始相对顺序。例如对[5a, 5b, 3]用a,b区分相同值建堆后第一次交换就可能破坏5a和5b的顺序。实操心得与对比堆排序在平均和最坏情况下都是 O(n log n)这点比快速排序最坏 O(n²)好但通常其常数因子比快速排序大所以实际运行速度往往不如优化过的快排。然而堆排序的亮点在于原地和最坏情况有保障。在内存紧张或对最坏运行时间有严格要求的场景下堆排序是一个可靠的选择。另外堆排序的交换次数相对较多。6. 小根堆原理相同规则相反理解了所有的大根堆操作小根堆就易如反掌了。小根堆的定义是每个节点的值都小于或等于其子节点的值。因此堆顶元素是整个堆中的最小值。如何将大根堆代码改为小根堆非常简单只需要在所有比较大小的逻辑上取反即可。siftUp将比较条件从heap[i] heap[parent]改为heap[i] heap[parent]。siftDown在寻找largest的地方改为寻找smallest并将比较条件从改为。buildMinHeap,heapInsert,heapPop等函数内部调用相应的siftUp或siftDown即可。小根堆的应用场景构建优先级队列获取最小优先级任务如 Dijkstra 算法中需要频繁提取当前距离最小的节点。求数据流中的 Top K 小元素维护一个大小为 K 的小根堆堆顶就是第 K 小的元素当新元素比堆顶大时就替换堆顶并下沉。哈夫曼编码需要反复合并频率最小的两个节点。7. 避坑指南与性能优化实战理论懂了代码写了但在实际项目中使用堆时还是会遇到一些坑。这里分享几个我踩过的雷和优化技巧。7.1 索引计算与边界检查这是最容易出 bug 的地方之一。务必确保在计算左右孩子索引 (2*i1,2*i2) 和父节点索引 ((i-1)/2) 时i的值是有效的。特别是在siftDown循环中判断left n和right n至关重要否则会数组越界。// 错误的示例忘记检查 left 和 right 是否越界 void siftDownBad(vectorint heap, int n, int i) { while (true) { int l 2 * i 1; int r 2 * i 2; int largest i; // 如果 l 或 r 大于等于 n下面的 heap[l] 访问就是非法的 if (heap[l] heap[largest]) largest l; if (heap[r] heap[largest]) largest r; // ... } }7.2 理解“原地”与“非原地”操作堆排序是“原地”的因为它直接在输入数组上操作。但很多情况下我们可能需要一个独立的堆数据结构。这时通常内部维护一个动态数组如 C 的vector Java 的ArrayList。在插入时动态扩容在删除时可能缩容。要了解你所使用语言中动态数组扩容的成本通常是均摊 O(1)但在对性能极其敏感的场景如果知道数据量上限可以提前reserve空间以避免多次扩容。7.3 自定义比较器与复杂数据类型实际应用中堆里存的往往不是简单的整数而是对象、结构体或键值对。例如在任务调度中堆里存的是(优先级, 任务ID)。这时我们需要定义如何比较这些元素。在 C 中可以通过重载运算符或为priority_queue提供自定义比较仿函数。在 Java 中可以为PriorityQueue提供Comparator。// C 示例存储 pair优先级, 任务ID希望按优先级最小堆 struct Task { int priority; int id; // 重载 运算符定义“小于”即优先级更高值更小 bool operator(const Task other) const { // 对于最小堆我们希望优先级数字小的在堆顶 // 但标准库的 priority_queue 默认是最大堆所以这里需要反向逻辑 // 更常见的做法是使用自定义比较器 return priority other.priority; // 注意这是为了适配默认最大堆的 trick } }; // 更清晰的做法使用自定义比较器 auto cmp [](const Task a, const Task b) { return a.priority b.priority; }; priority_queueTask, vectorTask, decltype(cmp) minHeap(cmp);注意C STL 的priority_queue默认是最大堆使用lessT其“顶”元素是最大的。如果你想实现最小堆需要提供greaterT或自定义返回a b的比较器。这是一个常见的混淆点。7.4 堆并非银弹选择合适的数据结构堆的强项是快速访问和删除最值O(1) 和 O(log n)。但它不擅长查找任意元素需要 O(n) 遍历。删除任意非堆顶元素需要先 O(n) 找到删除后还需要 O(log n) 调整。合并两个堆朴素合并是 O(n log n)有更高效的“可合并堆”如左倾堆、二项堆、斐波那契堆但实现复杂。如果你的场景需要频繁的任意查找或删除可能需要结合哈希表实现一个“索引堆”或考虑其他数据结构如平衡二叉搜索树。7.5 从“小土堆”到工业级实现网上很多教程包括一些热门的“小土堆”入门笔记为了简化实现的堆可能没有考虑异常处理、模板化、迭代器安全性等问题。在实际工程中一个健壮的堆实现应该模板化支持任意可比较数据类型。异常安全在pop空堆、peek空堆时有明确行为抛异常或返回特定值。提供迭代器如果需要但要注意堆的迭代器遍历顺序并不代表排序顺序。封装性将内部数组和核心方法siftUp/siftDown设为私有只暴露push,pop,top,size,empty等公共接口。最后再强调一次堆的思想是优美的其核心——siftUp和siftDown——是理解所有高级堆变种和优先级队列应用的基础。无论是解决 Top K 问题还是实现高效的调度算法当你意识到问题核心是“动态维护一个最值集合”时堆就应该成为你工具箱里的首选之一。
