堆排序是软考软件设计师下午题与上午题反复出现的经典考点，也是面试与算法竞赛中高频考查的数据结构。许多考生能背出"堆排序时间复杂度是 O(nlogn)"这句结论，却说不清堆为什么是一棵完全二叉树、建堆为什么是 O(n) 而不是 O(nlogn)、堆调整时下沉与上浮到底往哪个方向走。命题人恰恰喜欢在这些"看似会、其实不会"的细节处挖坑。本文从堆的定义出发，逐层拆解大顶堆与小顶堆的结构特征、堆的数组存储下标关系、建堆与堆调整的底层机制，再延伸到 Top-K 问题与优先队列的工程实现，最后落到历年真题的命题套路，帮助读者把堆排序从"背结论"变成"真掌握"。
堆在数据结构教材中的标准定义包含两个层次。第一层是结构性约束，堆必须是一棵完全二叉树，也就是除最后一层之外其余各层都是满的，并且最后一层的结点从左到右依次排列、中间不能留有空缺。第二层是序性约束，堆中的每个结点与其孩子结点之间满足统一的大小关系：如果每个结点的值都不小于其左右孩子结点的值，称为大顶堆，也叫做大根堆或最大堆；如果每个结点的值都不大于其左右孩子结点的值，称为小顶堆，也叫做小根堆或最小堆。
需要特别强调，堆的序性约束只规定了"父结点与孩子结点"之间的相对大小，并不要求兄弟结点之间、也不要求同一层的任意两个结点之间存在任何顺序。换句话说，在大顶堆中，根结点一定是整棵树里值最大的结点，但从根结点往下走，左孩子和右孩子谁大谁小是没有规定的。这一点与二叉排序树有本质区别：二叉排序树要求"左子树所有结点小于根、右子树所有结点大于根"，是一种全序的中序有序结构；而堆只保证"祖先大于后代"这一条偏序关系，中序遍历堆得到的序列并不一定有序。
从定义中还能引申出一个经常被忽略的事实：大顶堆的堆顶就是全体元素中的最大值，小顶堆的堆顶就是全体元素中的最小值，而且这一性质在整个生命周期中始终由堆序约束自动维护。这正是堆区别于普通完全二叉树的根本价值所在——普通完全二叉树只满足结构约束，结点之间没有任何大小关系，而堆把"取最大（最小）"这一高频操作从 O(n) 的线性查找压缩成了 O(1) 的常数时间读取。此外，完全二叉树还有一个常被混淆的近亲——满二叉树。满二叉树要求每一层结点数都达到最大值，即深度为 k 的满二叉树有 2 的 k 次方减一个结点；完全二叉树只要求最后一层可以不满、但必须从左到右连续排列。满二叉树一定是完全二叉树，完全二叉树却不一定是满二叉树。堆只要求是完全二叉树即可。
堆在逻辑上最常见的等价物是优先队列。优先队列是一种特殊的抽象数据类型，它支持两类核心操作：一是插入一个元素，二是取出并删除当前集合中优先级最高（或最低）的元素。堆恰好是优先队列最高效的实现载体，因为大顶堆的根结点恒为最大值，取最大值的操作可以在常数时间内完成，而删除根结点后的重新调整只需 O(logn) 时间。理解了这层关系，就能明白为什么 Top-K 问题、任务调度中的优先级管理、Dijkstra 最短路径算法中"每次选距离最小顶点"的贪心步骤，底层都离不开堆的身影。
不妨用一个具体数组把大顶堆和小顶堆的形态固化下来。给定关键字序列 45、78、23、56、12、89，若把它整理成一个大顶堆，根结点必然是 89；同一组数据若整理成小顶堆，根结点则变成 12。同一批数据、同一种完全二叉树结构，仅仅因为序性约束的方向不同，堆顶元素就发生了根本变化。理解这一点，有助于考生在构造题中快速判断：题目要求的是"最大优先"还是"最小优先"，从而决定选用大顶堆还是小顶堆。
堆的工程实现几乎一律采用数组，而不是链式结构，这是完全二叉树结构带来的天然优势。对于一个编号从零开始的一维数组，若把下标为零的元素当作根结点，那么任意一个下标为 i 的结点，其左孩子的下标是 2i+1，右孩子的下标是 2i+2，其父结点的下标是 (i-1) 向下取整除 2。有的教材采用下标从一开始的编号方式，此时左孩子为 2i、右孩子为 2i+1、父结点为 i 除以 2 向下取整，二者本质相同，只是下标偏移不同。正是因为完全二叉树每一层都从左到右紧密排列、没有空洞，才使得这种用下标直接计算父子关系的方式成立。
数组存储带来的第二个好处是内存紧凑、缓存友好。堆的操作始终在连续内存上按下标访问，不会像链式结构那样产生大量指针跳转，这在现代计算机的缓存层次结构下具有明显的性能优势。理解了数组下标关系，堆调整的代码逻辑就有了锚点：所谓"下沉"，就是从某个结点出发，反复比较它与其孩子结点，把不满足堆序性质的结点向叶子方向移动；所谓"上浮"，则是从某个结点出发，反复比较它与其父结点，把违反堆序性质的结点向根方向移动。
以一次具体的大顶堆下沉操作为例：假设某个结点比它的孩子小，违反了"父大于子"的约束，就需要把该结点与两个孩子中较大的那个交换位置；交换后，被移下来的结点可能仍然小于它在新的位置上的孩子，于是继续向下比较、继续交换，直到该结点重新满足大顶堆约束，或者到达叶子结点为止。这个过程每一次交换都让目标结点下降一层，最多下降树的高度这么多层，而完全二叉树的高度是 O(logn)，所以一次下沉调整的代价是 O(logn)。上浮则恰好相反：新插入的元素被放在堆的末尾，然后不断与其父结点比较，若新元素比父结点大（大顶堆），就交换并继续向上，直到到达堆顶或满足约束为止。删除堆顶的标准做法不是直接把根删掉，而是用堆中最后一个元素顶替根的位置，再对新的根执行一次下沉，从而在 O(logn) 内恢复堆序。这一"覆盖堆顶再下沉"的细节，是删除操作与插入操作在方向上的根本区别：插入用上浮，删除用下沉。
建堆是把一个无序数组整理成合法堆的过程。最直观也最容易被误用的做法是"逐个插入法"：从空堆开始，把数组元素一个一个插入，每次插入后做上浮调整。由于每插入一个元素都要沿着树的高度向上移动，总的时间复杂度是 O(nlogn)。这种做法虽然正确，却不是最优。
真正的做法是自底向上调整法，也叫 Floyd 建堆法。它的核心思想是：完全二叉树中下标最大的非叶子结点是最后一个结点的父结点，从这个结点开始，自右向左、自下而上地依次对每一个非叶子结点执行一次下沉调整。因为叶子结点本身已经满足堆的性质，无需处理，所以只需要处理大约一半的结点。关键在于，下沉调整的代价与结点所在的高度成正比，而完全二叉树中处于较低层的结点数量远多于处于较高层的结点数量，因此把所有结点的下沉代价加起来，得到的不是 nlogn，而是线性的 n。这就是"建堆是 O(n)"这一结论的数学根源。
不妨用一个规模较小的数组把自底向上建堆的过程完整走一遍。给定数组 50、45、40、20、25、35、10，最后一个结点的下标是 6，它的父结点下标是 2，对应元素 40，因此下标为 2、1、0 的三个非叶子结点就是需要依次做下沉调整的对象。先看下标 2 的结点 40，其左孩子是下标 5 的 35，没有右孩子，40 大于 35，无需调整；再看下标 1 的结点 45，两个孩子分别是 20 和 25，45 都大于它们，也无需调整；最后看下标 0 的根结点 50，它大于 40 和 45，同样无需调整。这个例子恰好本身就是一个大顶堆。若把根换成 30，则根结点 30 小于两个孩子中较大的 45，需要把 30 与 45 交换，交换后 30 落到下标 1 的位置，继续与其孩子 20、25 比较，30 仍大于二者，下沉结束。可以看到，每一步下沉都只沿着一条从父到子的路径向下推进，这正是自底向上建堆能在线性时间内完成的原因。
在完成建堆之后，堆排序进入正式的排序阶段。以大顶堆为例，根结点始终是当前无序部分的最大值。排序的每一步，都把根结点与当前无序区的最后一个元素交换，这样最大值就被"固定"到了数组的末尾，成为有序区的一部分；随后无序区的规模减一，新的根结点很可能破坏了堆序性质，于是对新的根结点执行一次下沉调整，重新恢复大顶堆。如此反复，直到无序区只剩一个元素，整个数组便从小到大排好了序。若要用堆排成从大到小的顺序，则改用小顶堆即可。
堆排序的完整时间复杂度由两部分构成：建堆的 O(n) 加上 n 次下沉调整的 O(nlogn)，整体为 O(nlogn)。堆排序是原地排序算法，除递归栈或临时变量外不需要额外数组，空间复杂度为 O(1)。同时，堆排序是不稳定排序，因为堆调整过程中父子结点交换会跨越多个元素，相同关键字的元素其相对次序可能被打乱。这几条结论——时间复杂度 O(nlogn)、空间复杂度 O(1)、不稳定——正是软考选择题反复考查的标准答案组合。
为了便于在纸上复现，可以把堆排序的完整过程总结为四步。第一步，把无序数组视为一棵完全二叉树，用自底向上调整法建成一个大顶堆；第二步，把堆顶元素与当前无序区的最后一个元素交换，此时最大值被放到数组末尾，有序区从无到有地产生了第一个元素；第三步，无序区规模减一，对新堆顶执行一次下沉调整，恢复大顶堆性质；第四步，重复第二步与第三步，直到无序区只剩下一个元素。由于每完成一次交换就确定一个最大元素并把它排除出后续调整范围，整个序列最终从左到右呈现从小到大的升序。
本篇完！