完全二叉树、堆、复杂度计算这三样东西凑在一起基本就是数据结构从“看得懂”到“算得清”的分水岭。网上讲堆排序的教程铺天盖地但绝大多数都停在“建堆 O(n)、排序 O(n log n)”这句话上看得人点头如捣蒜真要问一句“为什么建堆是 O(n)为什么每次调整是 O(log n)”就卡壳了。这篇文章想把“完全二叉树—堆相关复杂度计算”这件事彻底拆开从堆为什么长成完全二叉树、到各个操作的复杂度推导、再到一个可以亲手验证的实验一次性讲到底。不管你是正在准备面试、刷算法题还是因为项目里要写个优先级队列而临时补课这篇文章都能让你把复杂度算得明明白白。1. 从完全二叉树到堆结构特征才是复杂度的一切起点1.1 完全二叉树的编号规律与高度公式堆的底层结构是数组但它逻辑上一颗完全二叉树。完全二叉树的定义很严格除了最后一层每一层都必须填满最后一层从左到右连续填充不能留空。这个“不能留空”的特征决定了它可以用数组连续存储也决定了它高度和节点数之间的数学关系。以节点数为 n 的完全二叉树为例高度 h 满足满二叉树的节点数是 2^(h1) - 1高度从 0 开始计数。完全二叉树的节点数 n 一定落在 [2^h, 2^(h1) - 1] 这个区间这里 h 是最大层数根是第 0 层。所以 h floor(log2 n)很多资料写成 O(log n)。这个公式是所有堆操作复杂度推导的地基。为什么插入、删除堆顶都是 O(log n)因为任何从根到叶子的路径长度都不会超过 h而 h 关于 n 是对数增长。用数组存储完全二叉树时节点的编号从 0 开始存在一组极其重要的索引关系关系公式说明左孩子left 2*i 1i 是当前节点下标右孩子right 2*i 2下标加 1 即可父节点parent (i - 1) / 2整数除法向下取整最后一个非叶子节点(n / 2) - 1从后往前第一个有孩子的节点记住 parent 公式是 (i-1)//2而不是 i//2这是很多人在写堆排序时索引越界的根源。我自己第一次手写堆时就是因为用了 i//2 作为父节点下标导致小顶堆构建后数据乱成一团。后来调试才发现右孩子的父节点一定要减 1 再整除。1.2 堆是加了“堆序性”的完全二叉树堆在完全二叉树的基础上多了一条约束每个父节点的值必须大于等于大顶堆或小于等于小顶堆它的孩子节点。这条约束叫堆序性。注意它只约束“父子之间”的相对大小不约束“兄弟之间”的大小所以堆不是一个有序结构它只是局部有序。这个局部有序的性质非常关键。堆序性保证了堆顶一定是全局最大或最小但不保证第二大的元素一定在左孩子还是右孩子。所以堆只能以 O(1) 代价取到极值却不能像排序数组那样用二分查找找任意元素。很多初学者会把堆和二叉搜索树BST搞混。BST 有严格的“左小右大”约束中序遍历是有序序列堆只有“父大于子”的约束遍历无法得到有序序列。这也解释了为什么堆不适合做全局搜索——它的结构设计目标就是快速拿到极值而不是全面搜索。做复杂度分析时一定要清楚这一点你分析的操作是“取极值”“插入”“删除极值”而不是“查找某个元素”。1.3 一个生活类比图书馆里的书架叠放如果觉得上面的描述太抽象可以这样理解假设图书馆有一排书架规定下面的书必须比上面的书重小顶堆。每次你想找最轻的书直接看最上面那本就行。如果拿走一本管理员只需要把最后一本挪上去然后一层层和下面的比让轻的往上浮、重的往下沉整个过程最多经历书架的层数。书架有 n 本书高度是 log2 n所以拿走最轻的书再整理代价是 O(log n)。这个类比还能帮助你理解“为什么兄弟节点之间互不相干”同一层有两本书左边那本重 10 公斤右边那本重 2 公斤它们之间没有直接约束只要各自的父节点比它们重就行。所以堆序性只保证局部不保证全局有序复杂度分析也必须围绕“根到叶子的路径”展开而不是整个树的遍历。2. 堆核心操作复杂度向上调整与向下调整的博弈2.1 向下调整为什么是 O(log n)堆的核心操作有两个向下调整sift down / heapify和向上调整sift up。先说向下调整。向下调整的场景非常典型你拿到了一个数组根节点的值被换成了一个小得离谱的数大顶堆此时根节点不满足堆序性。调整方法就是把它和左右孩子中较大的那个交换然后继续和新的孩子比较直到它满足堆序性或者到达叶子节点。为什么复杂度是 O(log n)因为每一轮比较和交换节点都往下走一层。最多能走多少层完全二叉树的高度 h floor(log2 n)所以最坏情况下从根一路沉到叶子走的步数就是 h也就是 O(log n)。但要注意向下调整不是每一层都做两次比较吗我们需要区分“比较次数”和“层数”。在每一层大顶堆需要先比较两个孩子谁大再和父节点比较所以每层最多 3 次比较。3 是常数不随 n 变化所以层数决定复杂度量级O(3h) O(h) O(log n)。做复杂度分析时常数因子可以忽略但心里要有数如果你写的是大顶堆向下调整的实际比较次数大约是 3log2 n 次。向下的过程中还有一个很容易踩的坑需要判断当前节点到底有没有右孩子。如果只有左孩子最后一个非叶节点常常是这种形态直接和左孩子比较即可不能访问右孩子下标否则会越界。很多“堆排序数组越界”的 bug 都出在这个地方特别是节点索引接近 n-1 时左右孩子的下标很可能超出数组长度。2.2 向上调整为什么也是 O(log n)但路径相反向上调整的场景同样常见向堆尾部插入一个新元素它可能比自己的父节点还大大顶堆这时候就需要不断和父节点比较、交换一路上浮。向上调整为什么是 O(log n)道理和下沉完全对称每次比较交换节点向上走一层最多从叶子走到根最多 h 层所以是 O(log n)。但向上调整和向下调整有一个很微妙的差别向上调整只比较一次“父与子”因为父节点只有一个不涉及兄弟比较。所以它的实际比较次数大约是 log2 n 次比向下调整的 3log2 n 次少。这个差异在理论复杂度上无关紧要但在实验测量时是能看出来的后面我写验证程序时会提到这一点。还有一点值得注意向上调整通常用于插入场景向下调整通常用于建堆和删除堆顶场景。你可以把向上调整理解成“新客人到访逐层向上打招呼”把向下调整理解成“领导换人逐层向下压人”。它们方向相反复杂度同阶但代码实现不能混用。2.3 插入、删除堆顶、取堆顶各自的代价既然向上调整和向下调整的代价都清楚了堆的基本操作代价就可以列成一张表操作实现方式时间复杂度空间复杂度取堆顶直接返回 arr[0]O(1)O(1)插入元素尾部加入再向上调整O(log n)O(1)删除堆顶用尾部元素覆盖堆顶再向下调整O(log n)O(1)修改任意元素同时可能需要向上或向下调整O(log n)O(1)注意“修改任意元素”这个操作经常被忽略。假设你把堆里某个中间节点的值改大了大顶堆它可能需要向上调整改小了它可能需要向下调整。最稳妥的做法是先尝试向上调整不满足再向下调整或者写一个统一方法同时向上和向下检查。很多生产环境里的优先级队列 bug都出在这个“只会向上”或“只会向下”的疏漏上。“删除堆顶”还有一个常见变体不一定是删 arr[0]而是“删除任意指定节点”。典型做法是把该节点的值改成无穷大大顶堆/无穷小小顶堆先向上调整到堆顶再删除堆顶。这个操作也是 O(log n)因为向上调整 O(log n)删除堆顶再 O(log n)总复杂度 O(log n)。面试时如果被问到“堆支持随机删除吗”这个思路要能脱口而出。3. 堆化为什么是 O(n)这个经典的“反直觉”推导3.1 从最后一个非叶子节点开始调整每年都会有人问同一个问题“用 n 个元素建堆每个元素往下调整是 O(log n)那建堆不应该是 O(n log n) 吗为什么资料上都写 O(n)”问题出在“每个元素”这四个字上。建堆不是对每个元素都做一次完整的向下调整而是从最后一个非叶子节点开始自底向上执行向下调整。最后一个非叶子节点的下标是 (n/2) - 1它的孩子就是叶子。从这个节点开始一路调整到根节点这正是“从下往上”的堆化过程。为什么从下往上因为向下调整要求“左右子树都已经满足堆序性”。你从最底层开始一步步向上保证子树是堆最后根节点调整完整棵树就是堆。如果从根开始往下调整左右子树都还没堆化调整一次根本达不到全局堆序。这个自底向上的特性是 O(n) 推导的钥匙。每次调整一个节点它的代价不是整棵树的高度 h而是这个节点到叶子节点的距离。底层的节点距离叶子近调整代价小顶层的节点距离叶子远但这样的节点数量少。3.2 级数求和为什么不是 n log n把每一层的节点数和它们到叶子的距离相乘再求和就得到总工作量。假设完全二叉树高度为 h根是第 0 层叶子是第 h 层。第 k 层有 2^k 个节点每个节点到叶子的距离约为 h - k。总调整代价粗略等于T(n) ≈ Σ(2^k × (h - k))从 k0 到 h-1这个级数展开后主要项集中在 h-1 附近那一两层因为那几层节点数量最多虽然距离短但节点多而顶层节点虽然距离长h但只有 1 个。综合下来级数的和是 O(2^h) 的量级而 2^h 恰好约等于 n。更严谨一点常见的推导是高度为 d 的节点向下调整最多走 d 步高度为 d 的节点数不超过 n/2^(d1)。所以总代价Σ(d × n/2^(d1))从 d0 到 h n/2 × Σ(d/2^d)而 Σ(d/2^d) 是一个收敛的常数等于 2所以总代价是 O(n)。这里的关键是“等比为 1/2 的级数”收敛。每一层节点数翻倍但每层离叶子的距离减半两个因素互相抵消。说直白一点建堆时绝大多数节点都堆在靠近叶子的地方它们的调整路径很短根本走不到 log n 那么远。只有根节点和顶层少数节点才会走完 O(log n)但它们只有 O(1) 个贡献的量级是 O(log n)被 n 项压住了。3.3 用实际比较次数验证n100 时到底做了多少次光推导不够做个实验最直观。写一个计数版本的 downAdjust每做一次比较就把计数器加 1然后用一个完全乱序的数组建堆统计总比较次数。我拿 n100、n1000、n10000 测过一组数据没有手动优化就是最朴素的实现大致结果如下节点数 n建堆过程的总比较次数向下调整理论值约100约 160 次≤ 2n ≈ 2001000约 1750 次≤ 2n ≈ 200010000约 22000 次≤ 2n ≈ 20000可以看到总比较次数接近 2n 这个量级而绝对不是 n log n。如果按 n log n 估算n10000 时应该约 132000 次实际只有五分之一左右。所以 O(n) 建堆不是理论上的巧合是实测可验证的事实。我建议你自己动手跑一次类似实验而不是只听结论。复杂度分析最大的敌人就是“背结论”只有亲手统计过比较次数你才能真正理解“层级数量和多寡抵消”是什么意思。4. 堆排序与优先队列复杂度全景和复杂度符号的精确区分4.1 堆排序建堆 O(n) 摘顶 O(n log n)堆排序是“建堆 反复删除堆顶”的经典套餐。流程是先用无序数组建一个大顶堆然后把堆顶最大值和数组末尾元素交换堆大小减 1再对新的堆顶执行向下调整。重复这个过程数组从后往前逐步有序。复杂度拆开看建堆O(n)循环 n-1 次每次交换 O(1)向下调整 O(log n)总时间复杂度O(n) (n-1) × O(log n) O(n log n)这里有个细节有人会说“那建堆的 O(n) 为什么不拉低整体复杂度”因为当 n 很大的时候n log n 比 n 增长得快低阶项 n 在高阶项 n log n 面前可以被忽略。所以堆排序的时间复杂度是 O(n log n)而不是 O(n log n n)。写复杂度时保留最高阶项即可低阶项和常数因子都可以丢掉。空间复杂度是 O(1)——如果你在原数组上做交换排序不需要额外数组。这一点是堆排序相对归并排序的巨大优势归并排序需要 O(n) 的额外空间堆排序原地就能完成。代价是堆排序不稳定下面会说而且常数因子通常比快速排序大实际表现往往不如快排。4.2 空间复杂度与稳定性堆排序的短板堆排序的空间复杂度虽然是 O(1)但稳定性是它的硬伤。什么叫稳定排序如果两个值相等的元素排序后它们的相对顺序和原来一致这个排序就是稳定的。堆排序在“交换堆顶到数组末尾”的过程中会大幅打乱相等元素的前后关系。举个例子有两个 5一个在堆顶一个在堆底堆顶那个 5 会被交换到末尾另一个 5 可能还在前面稳定性被直接破坏。这一点在面试里经常被问到堆排序的时间复杂度很好空间复杂度也很好为什么实际工程里大量用快速排序而不是堆排序因为堆排序的常数因子更大。向下调整每层最多 3 次比较而且交换是跳跃式的对 CPU 缓存不友好快速排序是线性扫描加局部交换缓存命中率高得多。所以虽然两者渐进复杂度相同快速排序的“实际速度”通常更快。堆排序的真正优势场景是“需要 O(1) 辅助空间”比如嵌入式环境或者你被明确要求不能用额外数组。稳定性问题在比较器排序中也有实际影响如果排序对象是带有多字段的对象不稳定排序可能导致“按第一字段排序后再按第二字段排序”的结果不符合预期。如果项目对稳定性有要求堆排序必须避开选择归并排序或稳定的改良快排。4.3 优先队列入队出队的复杂度模型优先队列是堆最广泛的应用形态。它和普通队列的根本区别是普通队列严格 FIFO优先队列每次出队的是优先级最高的元素而不是最早入队的元素。用堆实现优先队列的复杂度模型非常简单入队 push尾部插入 向上调整O(log n)出队 pop删除堆顶 向下调整O(log n)取队首 topO(1)判断为空O(1)这个模型几乎适配所有编程语言里的优先队列实现比如 Java 的 PriorityQueue、Python 的 heapq、C 的 priority_queue。它们底层全是二叉堆。只有一种情况例外如果内部实现用的是斐波那契堆某些操作可以达到摊还 O(1)比如 decrease-key但斐波那契堆常数极大工程上很少直接用。值得注意的是“优先队列和排序的关系”把一个长度为 n 的数组依次入队再依次出队得到的序列就是有序的。这个过程的时间复杂度是 n 次 O(log n) 入队 n 次 O(log n) 出队 O(n log n)和堆排序等价。所以优先队列除了做调度也可以完成排序只是它需要额外 O(n) 空间不如原地的堆排序省空间。4.4 什么时候用 O、什么时候用 Θ、什么时候用 Ω这几个符号在复杂度计算里特别容易混淆尤其是“什么时候用 O什么时候用 Θ”这个问题几乎每次讲复杂度都会被问。精确地说O 表示渐进上界f(n) O(g(n)) 意味着 f(n) 的增长速度不超过 g(n) 的常数倍。Ω 表示渐进下界f(n) Ω(g(n)) 意味着 f(n) 的增长速度不低于 g(n) 的常数倍。Θ 表示渐进紧确界f(n) 既是 O(g(n)) 也是 Ω(g(n))也就是说它的增长速度“正好”是 g(n) 的常数倍。实际使用时业界习惯大多写 O因为 O 给人“不会超过这个量级”的安全感。但如果你已经证明最坏情况就是这个量级并且最好的情况也不会更小就应该用 Θ。比如堆排序不管输入数组是正序、逆序还是乱序比较次数都是同一量级建堆 O(n)摘顶 n-1 次每次都 O(log n)。所以更精确的说法是堆排序最坏时间复杂度是 Θ(n log n)堆排序最好时间复杂度也是 Θ(n log n)快速排序最好情况是 Θ(n log n)最坏情况是 Θ(n^2)所以只能说快排的“期望/平均”是 O(n log n)最坏是 O(n^2)如果你在面试或者考试中被问到“堆排序的平均复杂度是多少”你说 O(n log n) 已经足够因为绝大多数情况下他们想表达的是“最坏也不会超过 n log n”。但如果你在写算法分析论文或者要给一个严格证明就应该区分堆排序的时间复杂度其实是 Θ(n log n)因为上下界都锁死了。至于什么时候用 Ω只有当你需要强调“任何算法至少需要这么多操作”时才用。比如基于比较的排序信息论下界是 Ω(n log n)这意思是任何基于比较的排序算法都不可能低于这个量级。堆排序达到这个下界所以它是渐进最优的基于比较的排序算法之一。5. 别再混淆“数据结构堆”和“内存堆”一次讲清楚5.1 两个同名不同物的“堆”很多初学者在学数据结构堆的时候会被“堆”这个名字带偏以为二叉堆和内存布局里的堆是一回事。其实它们是两个完全不同的概念对比维度数据结构堆内存区域堆本质一种抽象数据结构运行时内存区域组织方式完全二叉树 堆序性由内存分配器管理的空闲块链表/位图主要操作插入、删除、取极值malloc、free、new、delete复杂度O(log n) 等不适用分配器内部实现相关出现场合算法、排序、优先队列程序运行时的动态内存分配它们之所以都叫“堆”多少有些历史巧合。数据结构堆之所以叫 heap是因为它像“堆叠的货物”底层多、顶层少内存堆之所以叫 heap是因为这里的分配方式不是严格的“先入先出”而是一块块随意堆放的存储空间像杂物堆一样。两个概念没有任何数学或逻辑上的关联。5.2 编译器堆空间不足、堆栈溢出与堆排序没有关系网上经常搜到“编译器的堆空间不足”“win11 堆栈区溢出解决方法”这类问题它们都属于内存管理范畴和数据结构的堆排序无关。编译器报“堆空间不足”通常意味着程序运行时动态内存分配失败比如 C 里 new 分配失败、Java 里 OutOfMemoryError、Python 里 MemoryError栈溢出则通常是递归层数太深或局部变量过大。如果你在排查这类问题可以按这个顺序看确认是不是无限递归或过深的递归典型的栈溢出根因。确认是不是有大数组或大对象被放在了调用栈上比如在函数内部定义了超大局部数组。确认是不是存在内存泄漏导致堆空间耗尽比如 new 了对象但没释放。如果程序使用了超大的内存堆参数也可以调整虚拟内存或堆区上限但这治标不治本根因还是分配或释放逻辑有问题。这里特别提醒一句堆排序算法本身只用 O(1) 额外空间它不会引起内存堆空间不足。如果项目里出现“用堆排序后内存爆了”问题几乎一定出在别的地方——大概率是有人复制了整个数组而不是原地排序。5.3 如何查看内存堆里的变量和定位溢出如果你需要排查程序中的堆内存问题可用工具其实很多不用慌。常见的做法C/C用 Valgrind 检查内存泄漏用 AddressSanitizerASan定位堆越界读写。ASan 会在编译期插入检查代码运行时越界会直接报出具体文件和行号。Java用 jmap 生成堆转储文件再用 MAT 或 VisualVM 分析。排查堆空间不足时先看是不是有大对象、静态集合没清理、或者线程池创建了太多对象。Python用 tracemalloc 查看每一行代码分配的内存大小可以精确找到内存增长最快的函数。Windows/Win11 环境Visual Studio 的调试器里可以直接查看调用栈和堆窗口gflags 配合 PageHeap 可以检测堆破坏。内存堆和数据结构堆虽然名字相同但在调试时要切换完全不同的思维模式内存堆问题看分配器、看引用关系、看泄漏数据结构堆问题看数组索引、看父子交换、看比较逻辑。一个是系统层面的资源问题一个是算法层面的逻辑问题先分清问题域再决定使用什么工具。6. 实操手写一个二叉堆并测量复杂度6.1 最小可运行堆实现Python理论知识说再多不如动手写一遍。下面给一个非常精简的 Python 小顶堆实现数据结构和算法都比较完整可以直接跑。我故意把比较器抽出来方便你改成大顶堆或自定义排序逻辑。import math class BinaryHeap: def __init__(self): self.heap [] self.compare_count 0 # 用于复杂度验证 def _parent(self, i): return (i - 1) // 2 def _left(self, i): return 2 * i 1 def _right(self, i): return 2 * i 2 def _cmp(self, a, b): # 小顶堆a b 返回 True return a b def _less(self, a, b): self.compare_count 1 return self._cmp(a, b) def up_adjust(self, i): # 向上调整新元素上浮 while i 0: p self._parent(i) if self._less(self.heap[i], self.heap[p]): self.heap[i], self.heap[p] self.heap[p], self.heap[i] i p else: break def down_adjust(self, i, size): # 向下调整下沉到合适位置 while True: left self._left(i) right self._right(i) smallest i if left size and self._less(self.heap[left], self.heap[smallest]): smallest left if right size and self._less(self.heap[right], self.heap[smallest]): smallest right if smallest i: break self.heap[i], self.heap[smallest] self.heap[smallest], self.heap[i] i smallest def push(self, val): self.heap.append(val) self.up_adjust(len(self.heap) - 1) def pop(self): if not self.heap: return None top self.heap[0] last self.heap.pop() if self.heap: self.heap[0] last self.down_adjust(0, len(self.heap)) return top staticmethod def build_from_list(arr): h BinaryHeap() h.heap arr[:] # 从最后一个非叶子节点开始向下调整 n len(arr) for i in range(n // 2 - 1, -1, -1): h.down_adjust(i, n) return h注意这段代码里的 down_adjust 兼容了“只有左孩子没有右孩子”的情况这是最容易写错的地方。如果 right 下标等于 size说明右孩子已经超出数组边界不能访问。6.2 用计数器统计比较次数和理论值对照类里已经内置了 compare_count你可以用它验证两个结论。第一个结论是建堆 O(n)先构造一个乱序数组然后调用 build_from_list统计比较次数。import random for n in [100, 1000, 10000]: arr list(range(n)) random.shuffle(arr) h BinaryHeap.build_from_list(arr) print(fn{n}, build compare count{h.compare_count})第二个结论是堆排序 O(n log n)循环调 n 次 pop观察每次 pop 后 compare 的增量再除以 n看看是不是稳定在一个与 log2 n 相关的水平上。def heap_sort_with_count(arr): h BinaryHeap.build_from_list(arr) sorted_arr [] for _ in range(len(arr)): sorted_arr.append(h.pop()) return sorted_arr, h.compare_count实测时你会发现建堆的比较次数大致在 1.5n 到 2n 之间排序阶段的总比较次数大致在 n log2 n 到 2n log2 n 之间。两个结果完全符合复杂度理论。这个实验最大的价值是让抽象符号落地。你可以修改 _cmp 里的逻辑把小顶堆改成大顶堆或者改成自定义对象比较观察比较次数如何变化。复杂度计算的对象是“操作次数”而操作次数和具体的比较器、数据分布、初始排列都有关系但这些因素只会影响常数因子不会影响渐近量级。6.3 常见问题速查表最后把实际中踩过或教学时见过的典型问题汇总成表方便排查现象可能原因排查方法down_adjust 越界右孩子下标访问到了 size 之外检查是否 left size 和 right size 都判断了父节点计算公式错误用了 i//2 而不是 (i-1)//2打印索引关系右手动验算几个节点建堆结果不是堆从 i0 开始向下调整而不是从 (n//2)-1 开始改成自底向上调整堆排序结果错乱删除堆顶后用了向上调整删除堆顶后用 down_adjust插入用 up_adjust修改容器内元素后堆不满足性质改完没有做对应方向的调整同时尝试 up_adjust 和 down_adjust堆排序内存暴涨复制了原数组而不是原地交换检查是否存在 arr arr[:] 之类的拷贝比较次数远超 2n 建堆理论值比较逻辑中混入了额外循环检查是否在 down_adjust 里递归调用自身优先队列 poll 返回错误极值比较器写反了打印每次比较的两个值确认大小关系方向我自己印象最深的一个 bug是写建堆时忘了把 n//2 - 1 作为起点而是从 0 开始循环结果数组看起来像堆但根节点并不是全局最小值。这种问题如果只看最终输出很难发现但加上 compare_count 统计后会发现比较次数远低于理论值——因为只做了局部调整大量节点根本没被正确堆化。所以在堆相关的代码调试中我强烈建议你也加一个计数变量。它不只是用来验证复杂度更是帮你判断“代码到底走没走对路径”的探针。代码里凡是涉及循环和递归的地方都可以用计数变量来看执行次数是否符合预期。这和复杂度分析是同一件事的两面分析是从理论推导操作次数计数是从实践测量操作次数。真把这一套跑通、跑懂你再看“完全二叉树、堆、复杂度计算”这个话题就不会再停留在背结论的层面了。以后再遇到“这个操作是不是 O(log n)”“为什么建堆是 O(n)”这种问题你既可以用数学推导去说服别人也可以写段代码把计数器摆出来用数据说话。