1. 堆排序到底在面什么：从一道高频题说起
面试季一到，算法题里出镜率最高的几个排序算法里，堆排序绝对排得上前三。很多人背了快排、归并的模板，唯独堆排序每次手写都卡壳——要么是建堆的时候下标算错，要么是下沉操作写成了上浮，要么是升序排序结果建了个小顶堆。我自己当年第一次面某公司的时候，面试官让我手写堆排序，我写完之后他问了一句“你建的是大顶堆还是小顶堆”，我愣了三秒才反应过来自己建反了。
这篇文章就是把我这些年反复讲堆排序、反复手写堆排序的经验整理出来。核心关键词是堆排序、Python实现、图解思路、面试算法。我会从“堆是什么”讲到“为什么升序要用大顶堆”，再到完整的Python代码实现和面试常见追问，尽量把每一个容易踩坑的地方都拆开讲清楚。适合正在准备面试的应届生、转行选手，也适合工作几年但想把基础重新夯实的朋友。读完你应该能做到：白板上手写堆排序不卡壳，面试官追问时间复杂度、稳定性、适用场景时能对答如流。
堆排序这个东西，光看代码觉得简单，但真正理解它“为什么这样设计”的人不多。我见过太多人能把代码背下来，但问他“为什么建堆要从最后一个非叶子节点开始”就答不上来。面试官恰恰最爱问这种“为什么”。所以这篇不只是给你代码，更重要的是把背后的逻辑链条讲透。
2. 堆的本质：一棵用数组装起来的完全二叉树
2.1 堆的定义与两种形态
堆（Heap）本质上是一棵完全二叉树，但它有个额外的性质：每个节点的值都大于等于（或小于等于）其子节点的值。前者叫大顶堆（Max Heap），后者叫小顶堆（Min Heap）。
这里有个关键点很多人一开始会混淆：大顶堆并不意味着数组是降序排列的，它只保证父节点大于等于子节点这个局部关系。比如数组[9, 5, 7, 3, 1, 6]，9是根，5和7是它的子节点，5的子节点是3和1，7的子节点是6。你会发现9比5和7都大，5比3和1都大，7比6大，满足大顶堆性质，但整个数组并不是有序的。
那为什么面试官这么爱考堆？因为堆这个结构同时具备两个很实用的特性：第一，它可以用数组紧凑存储，不需要额外的指针；第二，它能在O(log n)时间内完成插入和删除堆顶元素。这两个特性加在一起，就催生了优先队列这个数据结构，而优先队列在任务调度、Top K问题、Dijkstra算法里到处都是。
2.2 数组下标与父子关系的映射
用数组存堆的时候，下标关系是固定的。假设父节点下标是i，那么：
- 左子节点下标：
2 * i + 1 - 右子节点下标：
2 * i + 2 - 父节点下标：
(i - 1) // 2
这套映射关系是堆排序所有操作的基石。我建议你在纸上画一棵下标从0开始的完全二叉树，把每个节点的下标标出来，然后验证一下上面三个公式。这个动作花不了五分钟，但能帮你后面写代码的时候少犯一半的下标错误。
注意：有些教材用下标从1开始，公式变成
2*i和2*i+1，父节点是i//2。Python里我们统一用从0开始的下标，别混着用，混用是下标越界的第一大原因。
2.3 为什么用数组而不是链表
你可能会想，二叉树用链表存不是更直观吗？每个节点存左指针右指针。但堆有个特殊性质：它是完全二叉树，除了最后一层，其他层都是满的，最后一层节点靠左排列。这意味着数组里不会有“空洞”，每个位置都有意义。
用数组存的好处很直接：内存连续，缓存友好，而且不需要额外存储指针。在Python里虽然没有真正的连续内存数组（list底层是动态数组），但list的随机访问是O(1)，已经足够好了。用链表的话，每次找子节点都要跳指针，常数更大，代码也更啰嗦。
3. 堆排序的两大核心操作：上浮与下沉
3.1 下沉操作（sift down）：堆排序的主角
堆排序里最重要的操作是下沉，英文叫 sift down 或者 heapify。它的逻辑是：给定一个节点，如果它比子节点小（大顶堆的情况下），就和较大的那个子节点交换，然后继续往下比较，直到它比子节点都大，或者到了叶子节点。
为什么是和“较大的那个子节点”交换？因为交换之后要保证新的父节点比两个孩子都大。如果你和较小的子节点交换，那换完之后另一个子节点可能比新父节点还大，就不满足堆性质了。
我用一个具体例子走一遍。假设数组是[3, 9, 7, 5, 1]，我们对下标0的节点3做下沉：
- 3的左子节点是9（下标1），右子节点是7（下标2），较大的子节点是9
- 3 < 9，交换，数组变成
[9, 3, 7, 5, 1] - 现在3在下标1，它的左子节点是5（下标3），右子节点是1（下标4），较大的子节点是5
- 3 < 5，交换，数组变成
[9, 5, 7, 3, 1] - 现在3在下标3，是叶子节点，停止
最终[9, 5, 7, 3, 1]满足大顶堆性质。
下沉操作的时间复杂度是O(log n)，因为每次下降一层，树的高度是log n。
3.2 上浮操作（sift up）：建堆的另一种思路
上浮是插入元素时用的操作：新元素放到数组末尾，然后和父节点比较，如果比父节点大就交换，一直往上直到满足堆性质。
上浮和下沉的区别在于方向：上浮是从下往上调整，下沉是从上往下调整。建堆的时候两种方式都可以用，但效率不一样，这个后面会详细讲。
3.3 两种操作的代码实现
先看下沉的Python实现：
def sift_down(arr, n, i): """ 对arr[i]执行下沉操作 n: 堆的有效大小 i: 当前需要下沉的节点下标 """ while True: largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest == i: break arr[i], arr[largest] = arr[largest], arr[i] i = largest再看上浮：
def sift_up(arr, i): """ 对arr[i]执行上浮操作 """ while i > 0: parent = (i - 1) // 2 if arr[i] <= arr[parent]: break arr[i], arr[parent] = arr[parent], arr[i] i = parent这两个函数是堆排序的全部基础。我建议你先把这两个函数默写熟练，做到不看参考就能写出来，后面堆排序的主体逻辑就是在这两个函数上搭积木。
实操心得：写下沉的时候，用
largest变量记录当前最大值的下标，而不是每次都交换。先比较找出最大的，最后再决定要不要交换。这样比“发现一个就交换一次”少一半的交换操作，面试官看到会觉得你代码功底扎实。
4. 建堆：为什么从最后一个非叶子节点开始
4.1 自底向上建堆的完整流程
建堆的目标是把一个无序数组调整成大顶堆。做法是从最后一个非叶子节点开始，依次对每个节点执行下沉操作，一直到根节点。
最后一个非叶子节点的下标是n // 2 - 1。为什么？因为最后一个叶子节点的下标是n - 1，它的父节点是(n - 1 - 1) // 2 = n // 2 - 1。所有下标大于n // 2 - 1的节点都是叶子节点，叶子节点本身不需要下沉（没有子节点）。
建堆代码：
def build_heap(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i)就这么三行。但面试官可能会追问：为什么从后往前？为什么从最后一个非叶子节点开始？
从后往前是因为下沉操作依赖子节点已经是堆。叶子节点天然满足堆性质，所以从倒数第二层开始，每个节点的子树都已经调整好了，对它做下沉就能保证以它为根的子树是堆。一层一层往上推，最后根节点下沉完，整棵树就是堆了。
4.2 建堆的时间复杂度为什么是O(n)
这是面试里区分度很高的一个问题。很多人会想：每个节点下沉是O(log n)，一共n个节点，那建堆不就是O(n log n)吗？
实际上建堆是O(n)。原因在于：下沉的代价和节点所在的高度有关。叶子节点高度为0，不需要下沉；倒数第二层高度为1，最多下沉1次；倒数第三层高度为2，最多下沉2次。越靠近底层的节点越多，但它们的下沉代价越小；越靠近顶层的节点越少，下沉代价越大。
数学上可以证明，所有节点的下沉代价之和是O(n)。具体推导是：高度为h的节点最多有n / 2^(h+1)个，每个下沉代价是h，总和是n * Σ(h / 2^(h+1))，这个级数收敛到常数，所以总和是O(n)。
提示：面试时如果被问到这个问题，你可以先说“直觉上感觉是O(n log n)”，然后解释“但仔细分析会发现大部分节点都在底层，下沉代价很小，求和之后是O(n)”。这样回答比直接背结论更有说服力。
4.3 自顶向下建堆为什么更慢
另一种建堆方式是：从空堆开始，依次把每个元素插入到末尾然后上浮。这种方式的时间复杂度是O(n log n)，因为每个元素插入都要上浮，最坏情况下每个元素都要上浮到根。
两种方式对比：
| 建堆方式 | 操作 | 时间复杂度 | 实际表现 |
|---|---|---|---|
| 自底向上 | 从最后一个非叶子节点往前下沉 | O(n) | 更快，堆排序标准做法 |
| 自顶向下 | 依次插入并上浮 | O(n log n) | 较慢，但插入操作本身需要 |
堆排序里我们用的是自底向上建堆，因为数组已经全部给定了，不需要一个一个插入。
5. 排序阶段：为什么升序要用大顶堆
5.1 交换堆顶与末尾元素的逻辑
建好大顶堆之后，数组的第一个元素就是最大值。排序的思路是：
- 把堆顶元素（最大值）和数组最后一个元素交换
- 堆的有效大小减1（最后一个位置已经排好了）
- 对新的堆顶元素执行下沉操作，恢复堆性质
- 重复以上步骤，直到堆的大小为1
这个过程每次把当前堆的最大值放到数组末尾，所以最终数组是升序的。
代码：
def heap_sort(arr): n = len(arr) # 建堆 for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i) # 排序 for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] sift_down(arr, i, 0) return arr注意排序阶段下沉的时候，堆的有效大小是i，不是n。因为下标i及之后的元素已经排好序了，不能再参与堆的调整。
5.2 升序用大顶堆、降序用小顶堆的原因
这个问题面试官特别爱问。逻辑是这样的：升序排序意味着最大值要放到最后。如果我们用大顶堆，堆顶就是最大值，直接和末尾交换就完成了。如果用一个小顶堆，堆顶是最小值，你把它放到末尾，那末尾就是最小值，最后数组是降序的。
所以结论是：升序用大顶堆，降序用小顶堆。这个结论要记牢，面试时被问到不要犹豫。
5.3 完整排序过程图解
假设数组是[4, 6, 8, 5, 9]，我走一遍完整流程：
建堆阶段：
- 最后一个非叶子节点下标是
5//2-1 = 1，节点值是6 - 对下标1下沉：6的左子节点是5，右子节点是9，9最大，6和9交换，数组变成
[4, 9, 8, 5, 6] - 对下标0下沉：4的左子节点是9，右子节点是8，9最大，4和9交换，数组变成
[9, 4, 8, 5, 6] - 继续对下标1下沉：4的左子节点是5，右子节点是6，6最大，4和6交换，数组变成
[9, 6, 8, 5, 4] - 建堆完成，大顶堆是
[9, 6, 8, 5, 4]
排序阶段：
- 交换堆顶9和末尾4，数组变成
[4, 6, 8, 5, 9]，堆大小减为4 - 对堆顶4下沉：左子6，右子8，8最大，4和8交换，数组变成
[8, 6, 4, 5, 9] - 继续对下标2下沉：4是叶子，停止
- 交换堆顶8和末尾5，数组变成
[5, 6, 4, 8, 9]，堆大小减为3 - 对堆顶5下沉：左子6，右子4，6最大，5和6交换，数组变成
[6, 5, 4, 8, 9] - 交换堆顶6和末尾4，数组变成
[4, 5, 6, 8, 9]，堆大小减为2 - 对堆顶4下沉：左子5，4和5交换，数组变成
[5, 4, 6, 8, 9] - 交换堆顶5和末尾4，数组变成
[4, 5, 6, 8, 9]，排序完成
最终结果[4, 5, 6, 8, 9]，升序排列。
6. 复杂度、稳定性与适用场景全解析
6.1 时间复杂度逐阶段拆解
堆排序的时间复杂度分两部分：
- 建堆：O(n)
- 排序：n-1次交换和下沉，每次下沉O(log n)，总共O(n log n)
合起来是O(n log n)。注意建堆的O(n)被排序的O(n log n)吸收了，所以整体还是O(n log n)。
最好、最坏、平均情况都是O(n log n)，这一点比快排有优势。快排最坏情况会退化到O(n²)，虽然实际中很少遇到，但面试时如果问“哪个排序算法最坏情况也是O(n log n)”，堆排序和归并排序都是答案。
空间复杂度是O(1)，因为所有操作都在原数组上进行，只需要常数级别的临时变量。这是堆排序相对于归并排序的优势——归并需要O(n)的额外空间。
6.2 稳定性：堆排序为什么不稳定
稳定性指的是：如果数组中有两个相等的元素，排序后它们的相对顺序是否保持不变。堆排序是不稳定的。
原因在于交换操作是跳跃式的。比如数组[5a, 5b, 3]，建堆后可能变成[5a, 5b, 3]（已经是大顶堆），排序时交换堆顶5a和末尾3，变成[3, 5b, 5a]，然后下沉3，最终[3, 5b, 5a]。两个5的相对顺序变了。
面试时如果问“哪些排序是稳定的”，记住：冒泡、插入、归并、计数、基数排序是稳定的；快排、堆排、选择排序是不稳定的。
6.3 什么时候该用堆排序
堆排序的适用场景：
- 数据量大且对空间有要求，不能用归并排序的O(n)额外空间
- 需要保证最坏情况O(n log n)，不能接受快排的O(n²)风险
- 只需要找出Top K个元素，不需要完全排序（维护一个大小为K的堆即可）
不适合的场景：
- 数据量小的时候，插入排序反而更快（常数小）
- 需要稳定排序的时候
- 数据基本有序的时候，插入排序或Tim排序更合适
Python内置的sorted()用的是Tim排序，是归并和插入的混合，稳定且对部分有序数据有优化。所以实际开发中很少手写堆排序，但面试中它是考察你对树结构和数组操作理解程度的经典题目。
7. 面试高频追问与手写避坑指南
7.1 常见追问与参考回答
追问一：堆排序和快排比，哪个更快？
实际中快排通常更快，因为快排的常数因子小，缓存命中率高。堆排序的交换操作是跳跃式的，缓存不友好。但快排最坏情况O(n²)，堆排序稳定在O(n log n)。
追问二：Python的heapq模块和手写堆有什么区别？
heapq是小顶堆，只提供了heappush、heappop、heapify等函数，不支持自定义比较器（除非用元组包装）。手写堆可以灵活控制大顶堆小顶堆，也方便面试时展示理解。
追问三：如果要求找出数组中第K大的元素，怎么做？
维护一个大小为K的小顶堆，遍历数组，如果元素比堆顶大就替换堆顶并下沉。遍历完后堆顶就是第K大的元素。时间复杂度O(n log K)，空间O(K)。
追问四：堆排序能并行化吗？
比较难。堆的性质依赖全局结构，下沉操作有数据依赖，不像归并排序那样容易分治并行。
7.2 手写堆排序的五个常见错误
| 错误 | 表现 | 修正 |
|---|---|---|
| 建堆起始下标错误 | 从n-1开始遍历 | 从n//2-1开始 |
| 下沉时堆大小传错 | 排序阶段传n而不是i | 排序阶段传i |
| 子节点下标算错 | 用2i和2i+1 | 从0开始是2i+1和2i+2 |
| 升序建小顶堆 | 结果降序 | 升序建大顶堆 |
| 忘记更新i | 死循环 | 交换后i = largest |
7.3 白板手写的节奏建议
面试白板写代码，建议按这个顺序：
- 先写
sift_down函数，这是核心 - 写
heap_sort的建堆循环 - 写排序循环
- 用一个简单例子手动验证
不要一上来就写完整代码，先和面试官说清楚思路：“我先建一个大顶堆，然后每次把堆顶和末尾交换，堆大小减一，再下沉恢复堆性质。”说完思路再动手，面试官会觉得你逻辑清晰。
实操心得：白板写的时候，下标计算容易出错。我的习惯是先在旁边画一棵小树，标上下标，写代码的时候对照着看。这个动作花30秒，但能避免80%的下标错误。
8. 从堆排序延伸出去的知识点
堆排序只是一个入口，顺着它往下挖，能带出一串相关知识点。面试官如果对你印象好，可能会顺着堆排序往深了问。
优先队列：堆最直接的应用。Python的heapq就是优先队列的实现。任务调度、事件驱动模拟、Dijkstra算法都依赖优先队列。
Top K问题：从海量数据里找最大或最小的K个元素。用堆可以在O(n log K)时间内解决，比全排序的O(n log n)快。这是堆排序思想最实用的延伸。
堆与完全二叉树的关系：堆是完全二叉树，完全二叉树又可以用数组紧凑存储。这个性质把树结构和数组操作连接起来，是很多算法设计的基础。
其他堆变体：二项堆、斐波那契堆、左偏树。这些高级堆结构在特定场景下比二叉堆更优，比如斐波那契堆的插入是O(1)，但常数很大，实际中很少用。
堆在Python中的实际使用：heapq.heapify是O(n)建堆，heapq.heappush和heapq.heappop是O(log n)。如果你只需要小顶堆，直接用heapq就行，不用手写。需要大顶堆的话，可以存负数，或者用元组(-value, value)包装。
我自己在准备面试的时候，把堆排序手写了不下二十遍，每次都用不同的测试用例验证。后来发现，真正让我在面试中不慌的，不是背了多少遍代码，而是理解了每一步“为什么这么做”。理解了之后，即使紧张忘了某个细节，也能自己推导出来。
最后分享一个我常用的验证方法：写完堆排序后，用[3, 1, 4, 1, 5, 9, 2, 6]这个数组手动跑一遍，特别是有重复元素的情况，能帮你发现稳定性相关的问题。再跑一个已经有序的数组[1, 2, 3, 4, 5]和一个逆序的数组[5, 4, 3, 2, 1]，这三个用例覆盖了大部分边界情况。
