企业官网建设流程全解析

1. 为什么排序算法这么多，我偏偏觉得堆排序最值得手写一遍

如果要把排序算法按“出镜率”排个队，堆排序绝对不会是出场次数最多的那个，但它绝对是最值得手推一遍的算法之一。原因很简单：它把“树形结构”和“数组”这两件事焊在了一起，用完全二叉树的方式管理一段连续内存，再用交换代替插入，以O(nlogn)的时间复杂度完成原地排序。整篇文章不会只给你贴一段代码，而是把堆排序背后“为什么这样想”“为什么复杂度是这样”“手写时哪里容易崩”揉碎了讲清楚。适合正在准备算法面试、需要手写TopK方案、或者想彻底搞懂优先队列原理的开发者。

排序算法家族相当庞大：插入排序、选择排序、冒泡排序、归并排序、快速排序、计数排序、基数排序，每一个都有自己的脾气。堆排序在里面位置很特殊，因为它是少数几个“明明不怎么被当成默认排序用，却又到处都能看到其影子”的算法。你打开标准库里的PriorityQueue，底层就是堆；做海量数据TopK，堆是教科书级方案；操作系统任务调度、Dijkstra最短路的优化，同样离不开堆。所以理解堆排序，不只是学会一个排序算法，而是同时把二叉堆、完全二叉树、优先级队列、堆调整操作这一整套思想全部打通。

我见过不少朋友学堆排序时直接背代码，背得很快，但过两周再手写又崩了。这是因为堆排序的难点不在思路上，而在“数组下标映射”和“边界条件”这种细节上。只要你能用一句话说清楚“大顶堆里每个父节点都必须不小于子节点”，然后亲手写过几遍下沉操作，堆排序基本就是顺手的事。这篇文章我会从数据结构底层开始讲，到复杂度推导，再到边界坑点，最后聊聊它在真实工程里的定位。不求你背会一份万能代码，只求你看完之后，能在白板上心情平静地把它逼写出来。

2. 数组、完全二叉树和堆：先把“为什么数组能当树用”讲透

2.1 数组和完全二叉树的映射关系

堆排序里的“堆”，本质是一棵完全二叉树，而完全二叉树最大的好处是可以用数组连续存储，不浪费任何下标。打个比方，你把一棵树从上到下、从左到右一层层展开，每个节点对应数组里的一个位置，父子关系不用存指针，直接用下标算出来。

这里必须统一一个基准：数组下标通常从0开始，所以对于任意节点下标i：

• 左孩子下标是 2 * i + 1
• 右孩子下标是 2 * i + 2
• 父节点下标是 (i - 1) / 2，向下取整即可

如果你习惯从1开始编号，那公式会变成左孩子2i、右孩子2i+1、父节点i/2。我不建议在实现里混用这两种规则，绝大部分翻车现场都是因为一会儿用0基公式，一会儿又下意识套1基公式。这么多年的经验告诉我，直接用0基公式，写代码时不容易错，因为在大多数编程语言里数组天然是0基的。

2.2 大顶堆和小顶堆分别解决什么问题

二叉堆在具体业务里分为大顶堆和小顶堆。大顶堆的要求是：每个父节点的值都不小于它的两个孩子节点，所以堆顶一定是最大值。小顶堆反过来，父节点不大于孩子节点，堆顶一定是最小值。很多人会问：堆排序用的是哪个？如果是升序排序，就建大顶堆；如果是降序排序，就建小顶堆。这样设计是有讲究的，我们后面会看到，堆排序的核心循环是“把堆顶元素扔到数组末尾”，因此升序场景下用大顶堆，每次把最大值放到当前未排序区间的最后，正好形成递增序列。

大顶堆和小顶堆在很多场景下没有绝对的好坏，选择标准完全看你需要最快拿到最大值还是最小值。比如TopK问题里要求返回最大的K个数，你有没有想过为什么标准做法是用一个大小为K的小顶堆？因为当堆满K个元素后，新元素只要跟堆顶比较：当前堆顶是这K个候选里的最小值，如果新元素比它还小，那新元素肯定不属于最大K个；如果比它大，就替换堆顶并做下沉调整。这套逻辑用大顶堆反而麻烦，用大顶堆存“最大的K个”，你还得记录这K个里到底谁是最小的，每来一个新元素都要遍历一次，性能直接退化。

2.3 上浮和下沉：维护堆性质的两板斧

堆结构最重要的操作不是排序本身，而是维护“堆性质”的两种调整动作：上浮（sift up）和下沉（sift down）。

上浮用于往堆里插入新元素。插入的时候，我们先把新元素放到数组尾部，然后不断跟父节点比较：如果比父节点更适合做堆顶，就和父节点交换，一路往上走，直到满足堆性质或者到达根节点。这个操作最多走树的高度次，也就是O(logn)。

下沉则用于删除堆顶，或者用于建堆和堆排序的调整。以下沉为例，假设当前节点不满足堆性质，我们要在它的左孩子、右孩子中找到最大值（大顶堆场景）或最小值（小顶堆场景），然后和当前节点交换，交换后继续向下比较，直到该节点走到叶子位置或者已经满足堆性质。手写堆排序时，你只需要牢牢记住下沉函数，因为建堆、取堆顶、排序阶段的调整，全部复用这一个函数。

def sift_down(nums, n, i): # 下沉：大顶堆场景，n 表示当前堆的有效长度 while True: largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and nums[left] > nums[largest]: largest = left if right < n and nums[right] > nums[largest]: largest = right if largest == i: break nums[i], nums[largest] = nums[largest], nums[i] i = largest

这里必须强调一个细节：判断左右孩子下标时，第一步不是比较值，而是判断下标是否小于当前堆长度n。很多人写错堆排序，就是因为孩子下标越界或者没有意识到“堆长度会随着排序越来越短”。一旦你把下沉函数写对了，建堆和排序阶段只是换着方式调用它而已。

3. 堆排序三步走：建堆、交换、下沉，复杂度到底怎么算

3.1 建堆阶段为什么是O(n)，不是O(nlogn)

堆排序的第一步是建堆。如果数组已经是完全二叉树，只是堆性质不满足，我们要通过下沉操作把它调整成大顶堆。常规直觉是：堆排序整体O(nlogn)，那么建堆也应该是O(nlogn)。但真实复杂度是O(n)，这几乎是面试里最高频的误区之一。

为什么是O(n)？关键在于每个节点下沉的代价跟它所在的层高有关。叶子节点根本不需要下沉；倒数第二层的节点最多下沉1次；倒数第三层最多下沉2次……越靠近根部的节点数量越少，而它们需要下沉的次数越多。把每一层节点数和最大下沉次数相乘再求和，最终结果收敛于一个常数乘以n，而不是n乘以logn。

可以做一个粗略的计算。假设树高为h，根这一层有1个节点，最大下沉h次；下一层2个节点，最大下沉(h-1)次；再下一层4个节点，最大下沉(h-2)次……求和S = 1h + 2(h-1) + 4*(h-2) + ... ，这个等比加等差混合级数的结果趋向于2n。所以建堆阶段线性，这就是为什么自底向上建堆从倒数第二层再往上一层一层调整。

实现建堆时，我们需要找到“最后一个非叶子节点”。在0基数组中，这个节点的下标是 n // 2 - 1。因为叶子节点没有孩子，不需要调整。然后从该下标递减到0，逐个调用下沉函数。

def build_max_heap(nums): n = len(nums) for i in range(n // 2 - 1, -1, -1): sift_down(nums, n, i)

这里有一个极其容易踩的坑：循环必须从 n//2 - 1 递减到0，不能从0递增。我从0开始递增调整过一次，结果建出来的“堆”只能保证部分子树是堆，整个树根和子树之间仍然可能违反堆性质，排序结果自然就是错的。自底向上是堆排序铁律。

3.2 排序阶段：把最大值“扔”到末尾，再缩小堆范围

建堆完成之后，大顶堆的根节点就是全局最大值。排序阶段的核心循环很直接：

1. 把堆顶元素和当前堆的最后一个元素交换，这样最大值就被放到了数组末尾。
2. 将堆的有效长度减1，即把已经排好的元素排除在堆外。
3. 对新堆顶执行一次下沉操作，恢复大顶堆性质。
4. 重复上述过程，直到堆里只剩一个元素。

很多第一次写堆排序的人会问：不是要大顶堆吗？把最大值放到末尾之后，堆顶换成了一个小值，这个值下沉时会不会把更大的元素再顶上来？会，但这正是我们想要的。第二大的节点会成为新的堆顶，下一轮交换时，它会被放到倒数第二个位置。这样每一轮都拿走当前未排序区间的最大值，最终整个数组升序排列。

把代码串起来：

def heap_sort(nums): n = len(nums) build_max_heap(nums) for i in range(n - 1, 0, -1): nums[0], nums[i] = nums[i], nums[0] sift_down(nums, i, 0) return nums

注意这里sift_down的第二个参数传入的是i，而不是len(nums)。因为每交换一次，堆的有效长度就减少1，之前放到末尾的那些最大值已经属于有序区，不能再参与后续调整。这个“堆长度和数组长度不一样”的概念，是堆排序最容易出bug的地方之一。

3.3 完整代码和一个小例子

随便拿一个数组验证一下：如果输入[4, 10, 3, 5, 1]，建堆后得到[10, 5, 3, 4, 1]，第一轮交换堆顶10和末尾1，得到[1, 5, 3, 4, 10]，然后对前4个元素下沉，变成[5, 4, 3, 1, 10]。第二轮交换5和1，得到[1, 4, 3, 5, 10]，下沉前3个元素变成[4, 1, 3, 5, 10]。第三轮交换4和3，得到[3, 1, 4, 5, 10]，下沉前2个元素变成[3, 1, 4, 5, 10]，第四轮交换3和1，得到[1, 3, 4, 5, 10]。整个排序过程完全发生在同一个数组里，空间复杂度O(1)，这是堆排序引以为傲的原地特性。

测试时强烈建议多跑几个边界用例：空数组、只有一个元素的数组、所有元素相等、包含重复元素、包含负数。尤其是所有元素相等的情况，如果代码里比较符号写错，很容易出现意料之外的交换，虽然结果通常也是有序的，但过程会多做很多无谓操作。

4. 手写堆排序容易翻车的6个边界问题

4.1 左右孩子下标与父节点下标必须时刻对应

使用0基下标时，左孩子是2i+1，右孩子是2i+2，父节点是(i-1)/2。这三个公式是堆排序的生命线。我见过有人把左孩子写成2*i，还觉得没什么问题，结果在数组长度为偶数时得到完全错误的结果。调试方法也很简单：随意构造一个小数组，在sift_down函数里打印每个节点的下标关系和交换动作，一眼就能看出来是公式错了还是逻辑错了。

4.2 下沉时孩子节点可能不存在，必须检查下标范围

堆是一棵完全二叉树，但不是所有节点都有左右孩子。当i比较大时，左孩子可能已经超出堆长度，右孩子更可能不存在。所以在比较前必须先判断left < n和right < n。一个经典错误是直接访问nums[2*i+1]，如果越界就会抛出异常，或者在语言里读到脏数据。更隐蔽的错误是在right不存在时，还把nums[right]和nums[largest]比较，虽然某些语言下不会报错，但结果完全不可控。

4.3 堆长度必须随着排序过程动态更新

排序阶段每次交换后，末尾元素就固定了，下一轮不能再碰它。所以下沉时传入的n必须是当前堆有效长度，比如循环变量i。如果你一不小心写成len(nums)，已经排好的最大值又会被拉进堆里，不仅做无用功，还可能导致序列被重新打乱。这个问题的隐蔽性很强，因为它不是必然报错，而是偶尔结果正确、偶尔错误，非常难以排查。建议在代码里明确写一个heap_size变量，实时代表当前堆长度。

4.4 相等元素和稳定性问题

堆排序是不稳定排序。所谓稳定性，是指值相同的元素在排序后是否保持原来的相对顺序。为什么不稳定？因为在排序过程中，元素会跨越很长距离交换，比如堆顶和堆尾，这种“远距离搬迁”会打乱相同元素的先后顺序。举个例子，数组[2a, 1, 2b]（用下标区分两个值相等的2），建堆后2a和2b的位置可能已经交换，最终输出并不保证先出现2a再出现2b。如果业务中需要稳定排序，应该选择归并排序或插入排序，而不是堆排序。

4.5 建堆顺序：从最后一个非叶子节点倒着处理

前面我已经强调过，建堆必须从n//2 - 1递减到0。从0递增的错误在于：当调整根节点时，它下沉后可能会打破已经处理过的某个子树。比如根节点比右孩子小，交换后，新的右子节点可能又比右子子树里的节点小，但此时右子树已经错过调整时机，整个堆性质依然不成立。自底向上建堆则能保证每次下沉时，左右子树都已经是合法的堆，所以只要把当前节点下沉到正确位置，整棵子树就满足堆性质了。

4.6 递归和迭代的实现选择

sift_down既可以递归，也可以迭代。递归版本很简洁，但每次调用会产生函数栈开销，虽然堆高只有O(logn)，通常不会栈溢出，但在追求性能或处理超大数据量时，迭代版本更稳妥。更重要的是，递归版本容易让人忽略“交换后要继续向下检查”这一步。如果只交换一次就直接返回，那堆调整就只完成了一半，排序结果必然是错的。我建议初学阶段先写迭代版本，把循环写稳，以后再改成递归也不迟。

5. 堆排序的真实定位：TopK和优先队列里它才是主角

5.1 TopK问题：堆是无可替代的常客

如果你只需要从海量数据里挑出最大的10个数，而数据量大到无法一次性全部载入内存，堆排序的选择性调整能力就体现出来了。维护一个大小为10的小顶堆，依次扫描数据，每一轮最多做一次堆顶替换和下沉，时间复杂度为O(nlogK)。K通常是几十、几百，复杂度几乎可以看成O(n)。这种场景下，快速排序反而不好办，因为快速排序需要把整个数组都读进来才能排序。

类似的场景还有合并K个有序链表、滑动窗口最大值、数据流中位数。中位数问题通常用两个堆实现：一个大顶堆存放较小的一半，一个小顶堆存放较大的一半，保持两边元素数量差不超过1。这些题目表面上是数据结构题，内核全都在考堆的维护和堆排序的下沉、上浮操作。

5.2 堆排序作为通用排序的短板：缓存局部性和常数因子

既然堆排序复杂度稳定、空间原地，为什么标准库默认排序不用它？答案是常数因子和缓存局部性。堆排序的访问模式像“跳楼梯”：当前节点和它的孩子可能在数组里相距很远，交换完之后还要跳去访问再下一层的孩子。CPU缓存对连续内存访问非常友好，而堆排序这种跳跃式的访问容易反复没命中缓存。相比之下，快速排序是分块分区处理，归并排序虽然是额外空间，也能按连续片段读写，缓存命中率要好看得多。

实际跑数据时，堆排序在随机整数数组上通常比快速排序慢两到三倍，这还没有计算递归或函数调用的开销。所以在通用排序库的实现里，你几乎见不到单纯堆排序，Java的Arrays.sort对基本类型使用双轴快速排序，对对象使用TimSort；C++的std::sort则通常使用内省排序，快排递归深度过深时切回堆排序来避免最坏情况。

5.3 堆排序、快速排序、归并排序怎么选

这张表能回答大多数“为什么这个场景不用堆排序”的问题。如果你明确要求原地、稳定，堆排序做不到稳定；如果你要快，堆排序常数大；但如果你要处理动态数据、随时取最大值，堆排序是不二之选。所以看待堆排序的正确姿势是：它是一个优秀的“优先级管理”工具，而不是一个“通用数组整理”工具。

5.4 标准库有堆，为什么还要能手写

很多语言已经提供了现成的堆实现，比如Python的heapq，Java的PriorityQueue，C++的priority_queue。日常工程开发里，直接调库是最稳妥的选择。那为什么我仍然建议你手写？一方面，面试经常让你实现堆排序或堆结构，调库等于零分；另一方面，调库只是黑盒，你迟早会遇到需要自定义堆调整逻辑的时刻。比如Dijkstra算法里用索引堆优化，需要动态修改某个节点的优先级，标准库的优先队列做不到高效修改，这时你必须理解堆的内部结构，才能手工实现索引堆。

6. 从堆排序到算法思维：一些不成熟的实战建议

6.1 闭卷手写堆排序的考场技巧

如果你正在准备面试，我建议把堆排序的代码分成三个记忆块：sift_down下沉、build_max_heap建堆、heap_sort排序循环。核心记忆点是下沉函数的不变量：调用它之后，以传入节点为根的子树必须重新满足堆性质。只要把这个不变量刻在脑子里，不管你从哪个数据规模开始写，都不容易跑偏。

书写顺序上，先写sift_down，再写建堆，最后写排序循环。这样写的好处是每步都能独立验证：只跑sift_down可以检查它是否把子树调整正确；只跑建堆可以打印整个数组看是否符合大顶堆；最后再跑完整排序。此外，写完代码后一定要手动跑一个长度为3到5的数组，展开成完全二叉树画出来，对照数组检查每一轮交换后的状态。这样做上三遍，基本就不会再忘了。

6.2 堆排序教给我的，不只是排序

我个人在实际项目里，直接调用堆排序的场景其实很少，但“堆”这个数据结构几乎每天都在用。任务队列根据权重调度，直接用优先队列；电商推荐需要实时取点击率最高的商品，也是堆结构。我越来越觉得，堆排序最大的价值不是让你多掌握一种排序手段，而是让你建立一种“局部有序即可”的思维：与其每次把全部数据整理得干干净净，不如维护一个始终能快速取出最大值的结构。系统里很多性能问题，本质上都是因为“过度排序”，比如为了取最大值把整个数组排好序，白白花了O(nlogn)，如果换成堆，只要O(n)建堆和O(1)取顶。

如果你以后要深入数据结构的变体，堆这条路还能继续往下走：索引堆、二项堆、斐波那契堆、左式堆、配对堆，每一层都建立在“堆性质”这个地基上。但无论变体多复杂，最底层的思想仍然是这里讲的“一棵完全二叉树、两种调整动作、一个堆顶”。先把这篇里的数组下标和下沉函数吃透，再去看那些高阶堆，你会发现它们其实就是同一棵树的远房亲戚，没什么神秘的。