堆排序原理与Python实现：从建堆到排序的完整拆解

因为堆排序这个主题在算法题和面试里太常出现，但很多人写起来总是磕磕绊绊——要么建堆的循环边界搞错，要么堆化函数写得云里雾里，要么排序结果出来之后自己都解释不清为什么是对的。我决定把堆排序的完整实现拆开讲透，从原理到代码再到实际跑数据的表现，一次性把这个"看似简单实则容易翻车"的排序算法讲明白。

这篇文章适合正在学数据结构的初学者，也适合准备算法面试、看了很多讲解但仍写不出干净代码的人。我会用Python实现一版最直白的堆排序，然后沿着"为什么这么写、哪里容易错、实际性能如何、什么场景才值得用它"这条线往下走，最后给出一些我自己实测后觉得很有价值的替代方案和工程建议。

1. 堆排序到底在排什么：先分清"建堆"和"排序"两个阶段

不少人学堆排序的时候，会被"堆"这个词劝退。其实你不需要把它想得多高深，堆本质上就是一棵完全二叉树，并且在这棵树里，父节点的值永远比子节点大（或小）。如果父节点最大，叫最大堆；父节点最小，叫最小堆。我们做升序排序用最大堆，做降序排序用最小堆，这是第一步需要明确的。

堆排序的核心思想也很粗暴：把一个无序数组先整理成合法的大顶堆，此时堆顶就是全局最大值；把堆顶搬到数组末尾，这个最大值就归位了；然后对剩下的部分重新堆化，再次拿到第二大值，继续搬，循环往复。听起来就像"反复从堆里摸出最大的再扔掉"，而"摸"的动作只需要O(1)时间，"重新堆化"只需要O(log n)，所以整体复杂度是O(n log n)。

这里有一个容易混淆的点：很多人以为堆排序要先构建一个完整的堆结构，再挨个弹出最大值。实际上，数组本身就能表示一棵完全二叉树——下标i的左孩子是2i+1，右孩子是2i+2，父节点是(i-1)/2。所以建堆不是新建一棵树，而是通过交换数组内元素的位置，让数组满足"每个父节点大于等于子节点"的性质。这个阶段叫建堆（heapify）。

建堆完成之后，把堆顶和当前未排序区间的最后一个元素交换，接下来最关键的是注意：交换后堆顶被破坏，你需要从堆顶开始往下重新堆化（sift_down），但这次堆的规模要减一，因为排好的最大值已经不需要再参与比较了。重复这个动作，直到未排序区间的长度变成1，排序自然完成。

很多文章把这两个阶段混在一起讲，导致读者总觉得堆排序"好像懂了但写不出来"。我的经验是先在心里把代码分成两个函数：一个负责"从某个节点往下调整堆"，另一个负责"主流程调用调整"。这样结构清晰，调试也方便。

另外，堆排序是一个原地排序算法，这是它和归并排序最大的区别之一。它不需要额外的大数组来暂存数据，只需要在交换元素时用几个临时变量，空间复杂度是O(1)。这在内存受限的环境里是很大的优势。理解了这些前置概念，我们再来看具体怎么用代码落地。

2. 用代码把堆排序拆开：建堆循环为什么从n//2-1开始

我直接给出一个最直白、最容易看懂的Python实现，后面会逐行解释。这里故意不做什么花哨的优化，纯粹为了把逻辑讲清楚。

def sift_down(arr, i, heap_size): """ 从节点 i 开始向下调整，使 arr[0:heap_size] 维持最大堆性质 """ while True: largest = i left = 2 * i + 1 right = 2 * i + 2 if left < heap_size and arr[left] > arr[largest]: largest = left if right < heap_size and arr[right] > arr[largest]: largest = right if largest == i: break arr[i], arr[largest] = arr[largest], arr[i] i = largest def heap_sort(arr): n = len(arr) # 阶段一：建堆 for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n) # 阶段二：逐个取出堆顶 for end in range(n - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] sift_down(arr, 0, end) return arr

2.1 sift_down内部循环：为什么要比较两次再决定谁当largest

sift_down做的事情很简单，从某个节点出发，看它的左孩子和右孩子谁更大；如果孩子里有比当前节点还大的，就把最大的那个换到父节点位置；然后继续往下，沿着交换后的路径再检查，直到没有孩子比它大为止。

我用了while True而不是递归，主要是为了避免递归调用栈的深度问题。虽然堆排序的树高一般是O(log n)，递归问题不大，但while写法在工程上更实用，也能让不熟悉递归的人更容易理解。

注意一个细节：我需要比较两次，一次左孩子，一次右孩子。很多人会写一个if arr[left] > arr[right]再比较，这其实也能做，但不够优雅。先假设largest = i，然后用left和right依次挑战它，这样代码更简洁，也避免了左右孩子下标可能越界的问题。比如当left >= heap_size说明当前节点已经没有左孩子了，那它肯定也没有右孩子（完全二叉树的性质），直接break即可；当只有左孩子没有右孩子时，第二个if right < heap_size会自然跳过。

2.2 建堆为什么从最后一个非叶子节点开始退着走

这里是最多人困惑的地方。我们要建堆的初始数组是乱序的，如果从根节点开始向下调整，会出现一个尴尬的情况：根节点沉下去之后，它原本以为"底下已经是大顶堆了"，可实际上底下的子树根本还没调整过，整个堆性质就不成立。

所以正确的做法是从最后一个非叶子节点开始，先让下面的小子树各自满足堆性质，再一步步往上，让更大的子树也满足。最后一个非叶子节点的下标是n // 2 - 1，这个公式怎么来的？因为完全二叉树中最后一个节点的下标是n - 1，它的父节点下标是(n - 1 - 1) // 2，也就是n // 2 - 1。从它开始往前遍历到0，就能保证每个节点在它的子树已经是合法堆的前提下再做向下调整，最终整棵树变成一个合法大顶堆。

这个过程复杂度是O(n)，而不是很多人以为的O(n log n)。直观理解就是：堆中越靠近底层的节点数量越多，但它们只需下沉很少的层数；越靠近根部的节点数量越少，但它们下沉的层数多。整体算下来，总工作量是线性的。这里不展开数学推导，但你可以记住结论：建堆是O(n)，排序阶段才是O(n log n)。

2.3 排序阶段：交换堆顶和末尾，再把新的堆顶沉下去

建堆完成后，数组已经满足"父节点大于子节点"，但整个数组还远没有排好序。排序阶段的第一步是拿堆顶arr[0]（最大值）和当前区间最后一个元素arr[end]交换，这样最大值就被送到了它最终应该在的位置。

但交换之后，新的arr[0]通常是一个很小的值（之前被换到末尾的某个值），此时堆顶被破坏。不过好消息是：除了堆顶之外，其他部分仍然满足堆结构，所以只需要对下标0执行一次sift_down，让这个倒霉的小值一路沉到它该去的位置即可。heap_size传入end，而不是n，是因为从end开始往后的部分已经是排好序的大数，不能再让它们参与堆调整。

循环的终止条件是end到1，因为当只剩下一个元素时，它一定是全局最小，天然排好了。到这里，堆排序就完成了。

3. 最容易踩坑的细节：索引边界、稳定性和错误测试

代码写完了，但直接拿去跑，大概率会碰到几个经典问题。我把这些坑单独拎出来说，因为它们才是"简单实现"背后的真正门槛。

3.1 边界条件：left和right必须严格小于heap_size

这是堆排序里最常见的bug来源。我在代码里写的是if left < heap_size and arr[left] > arr[largest]，这个left < heap_size是不可省略的。很多人知道要判断，但容易漏掉特殊情况：当某节点只有左孩子、没有右孩子时，右孩子的下标2*i+2可能刚好等于或超过heap_size，如果不去判断，就会发生数组越界或拿到脏数据。

我建议在所有涉及孩子节点的地方都统一检查边界，不要图省事。尤其当你把sift_down单独抽出来做单元测试时，各种边界值（n=1、n=2、n=3、n=2的幂次）都要测一遍。

3.2 稳定性：堆排序为什么不是一个稳定排序

必须清楚地认识到，堆排序是不稳定的。原因也很直观：在sift_down过程中，相同的值可能会因为堆的调整而交换相对顺序。

举个例子，假设数组里有两个相同的数字5a和5b，在堆调整中，5a可能被从父节点位置换到子节点，然后又和5b交换，最终5b跑到了5a前面。这个行为在调试时很容易被忽略，因为数值相同，排序结果看起来也没差别；但在实际业务中，如果排序的对象是对象数组，且需要保持某个字段相等时原有的顺序，堆排序就无法保证。

如果你需要稳定排序，请选择归并排序的稳定变体或插入排序，或者用额外的下标作为第二排序键来达到"伪稳定"的效果。很多候选人面试时被问到"堆排序稳定吗？"，答案一定要斩钉截铁：不稳定。

3.3 只想升序却建了小顶堆：方向搞反的典型症状

另一个很常见的坑是搞错建堆类型。升序排列需要最大堆，因为我们要"每次把最大放到末尾"。如果误建成了最小堆，堆顶是最小值，你把它放到末尾，得到的是一个降序数组。更麻烦的是，如果你没有意识到问题，可能会通过reverse来"补救"，结果代码看起来能跑，但逻辑已经绕了远路。

我的建议是先在纸上手动模拟一遍小例子，比如[4, 10, 3, 5, 1]，确认"建最大堆->交换->收缩堆->调整"的顺序，再到代码里验证。这样能从根上避免方向性错误。

3.4 别忘了测试空数组和单元素数组

写排序算法时，测试空列表[]和单元素列表[42]应该成为肌肉记忆。堆排序对这两个输入都应该直接返回原列表，代码里n = len(arr)，如果n为0或1，range(n // 2 - 1, -1, -1)分别是range(-1, -1, -1)和range(0, -1, -1)，都不会执行任何循环，第二个for end in range(n - 1, 0, -1)也根本不会进入，所以直接返回即可。

这一点在工程上很重要：很多排序函数被封装成公共组件后，第一个调用的场景可能就是空数据或单条数据。如果在这里崩了，哪怕是其他地方完全正确，也会给人留下不严谨的印象。

4. 实测跑一遍：小数据到大数据的性能表现与常数开销

堆排序的复杂度是O(n log n)，理论上和快速排序、归并排序同级，但实际跑起来差别不小。我用几个不同规模的数据做了简单测试，环境是普通个人电脑，Python版本用解释器运行，排序对象是无重复的随机整数列表。

（耗时因机器差异会有波动，但数量级关系是稳定的。）

从测试可以看到，堆排序在小数据时比内置排序慢一个数量级，在大数据时差距也依然存在。原因主要是两点：第一，Python里纯实现的循环和交换操作比C语言实现的内置排序慢太多；第二，堆排序的访问模式对缓存不友好，它经常在相隔较远的数组位置之间跳跃，而快速排序是顺序遍历，缓存命中率高很多。所以当你写的是纯Python堆排序时，别指望它和内置的list.sort()掰手腕。

但如果你用的是C语言或者对常数项要求不那么敏感的静态语言，堆排序的性能差距会缩小很多。而且它有一个不可替代的优势——无论数据初始分布如何，时间复杂度都是O(n log n)。快速排序在最坏情况下会退化到O(n^2)，而归并排序虽然稳定，但需要O(n)的额外空间。堆排序在这两个维度上做到了稳定且省空间。

我还实测了堆排序在"几乎有序"数据上的表现，结果并不理想。它不会像插入排序那样利用已有顺序加速，依然老老实实地做完整的建堆和交换，所以如果你处理的是接近有序的数据，请优先考虑插入排序或内置的Timsort。

5. 在工程里什么时候才真正需要"手写"堆排序

聊完了性能，我想给你一个更实际的经验：绝大多数业务场景里，你不该自己实现堆排序去和list.sort()比拼。但"堆"本身这个数据结构在工程里太常用了，它才是你真正该从堆排序里带走的核心资产。

5.1 TopK问题：比全排序更省内存的做法

面试和业务里经常遇到"从海量数据中找出最大的K个元素"。如果直接用堆排序把整个数据集排序，时间和空间都浪费在明明不会用到的那些元素上。正确的做法是维护一个大小为K的最小堆，遍历数据时，只要堆不满就直接入堆；堆满了之后，如果新元素比堆顶（当前堆里最小的那个）大，就替换堆顶并调整堆。这样最终堆里留下的就是最大的K个，时间复杂度O(n log K)，空间O(K)。

这就是"堆排序里的sift_down能力"的迁移应用。我在处理百万级日志数据时经常用这个思路，只保留Top100，内存占用稳定可控。

5.2 优先队列：定时器、任务调度的底层依赖

堆排序的另一个大名鼎鼎的应用是优先队列。比如操作系统的定时器，需要快速找到"下一个到期的任务"，如果遍历整个任务列表，每次都是O(n)；而用最小堆存储任务，取堆顶只是O(1)，插入和删除堆顶都是O(log n)。

Python的heapq模块就是干这个的。大多数时候你根本不需要自己手写堆，直接用heappush和heappop就好。但如果你理解了sift_down的原理，就很容易明白heapq的接口为什么是那样设计的，出问题时也能更快定位。

5.3 外部排序和大数据场景

当数据量大到无法全部加载进内存时，堆排序可以参与多路归并的过程。比如把大文件切分成多个有序的小块，然后用一个大小为M的堆来做多路归并，每次从M个输入流中取最小的一个写入输出文件。这里的"堆"就是归并的加速器，而不是用来做完整排序的。

如果面试官让你"在不使用额外大量内存的前提下，对超大文件排序"，你要想到的其实是外部排序+堆的配合，而不是单纯堆排序。这是堆这个数据结构在工程上最有含金量的场景之一。

5.4 堆排序不太适合的场景

反过来，我也想把"不该用堆排序"的场景说透。如果你要排序的对象是链表，堆排序的随机访问优势就完全发挥不出来，优先考虑归并排序；如果你需要的是稳定排序，堆排序直接出局；如果你的数据量很小（比如几十个元素），插入排序的代码更简单，实际速度也更快；如果你不需要原地排序，那么内存换速度的归并排序往往更合适。

在工程选型上，我一般会按这个顺序考虑：数据近乎有序选插入排序/内置Timsort；需要稳定且数据规模大选归并；内存极度紧张且需要O(n log n)最坏复杂度才考虑堆排序；海量TopK选堆而不是全排序。先想清楚场景，再决定是否手写。

6. 让实现更健壮的进阶技巧：从"能跑"到"好用"

如果你不只是想应付面试，而是真的要把堆排序变成一个可复用的工具函数，还有一些细节值得打磨。

6.1 支持自定义比较器

上面的实现仅支持数字的升序排序。在实际项目中，你可能要按对象的某个属性排序，或者需要自定义比较规则。最简单的做法是在sift_down中传入一个比较函数key，或者用一个less_than函数。但要注意，一旦引入key或比较器，性能会进一步下降，因为每次比较都多一层函数调用。对于性能敏感的场景，建议直接用传入的比较器重写代码，而不是定义一个通用但缓慢的版本。

def heap_sort_by(arr, key=lambda x: x, reverse=False): n = len(arr) lt = (lambda x, y: key(x) < key(y)) if not reverse else (lambda x, y: key(x) > key(y)) def sift_down(i, size): while True: target = i left = 2 * i + 1 right = 2 * i + 2 if left < size and lt(arr[target], arr[left]): target = left if right < size and lt(arr[target], arr[right]): target = right if target == i: break arr[i], arr[target] = arr[target], arr[i] i = target for i in range(n // 2 - 1, -1, -1): sift_down(i, n) for end in range(n - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] sift_down(0, end) return arr

这段代码通过key函数把比较逻辑抽取出来，同时用一个lt闭包来控制升降序。注意我用的是"把目标值从子节点挑战到父节点"的思路，而不是直接写arr[left] > arr[right]，这样逻辑更通用。

6.2 递归版 vs 迭代版的选择

我在主实现里给了迭代版sift_down，主要是因为我不想让递归调用栈深到不可控。虽然堆的高度是O(log n)，在百万级数据下也才20多层，递归完全没问题；但迭代版在工程上更直观，也不会被极端输入坑到。

如果你更习惯递归，可以这样写：

def sift_down_recursive(arr, i, heap_size): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < heap_size and arr[left] > arr[largest]: largest = left if right < heap_size and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] sift_down_recursive(arr, largest, heap_size)

两种方式在功能上没有区别。递归版短小精悍，迭代版避免调用开销。我个人在调试时更喜欢迭代版，因为可以用打印语句一行行观察i的移动路径。

6.3 原地排序的边界注意：不要误把已排序区间的元素卷入堆化

在排序阶段的循环里，sift_down(arr, 0, end)中的end是当前未排序区间的大小，而不是数组长度。这一点非常容易被忽略。如果你在排序阶段误传了n，那么已经被排到末尾的那些"大数"会再次参与堆调整，虽然最终结果可能仍然正确（因为大数不会再被交换到前面），但会做很多无用的比较，性能受损，而且逻辑上也不干净。

我在写第一版堆排序的时候，就在这个参数上翻了车。排序结果偶尔正确、偶尔不正确，调试了半天才发现是heap_size传错了。现在我会在代码里把参数名写成heap_size而不是n，以提醒自己这代表的是堆的当前有效大小。

7. 我也曾经犯过的错误与最终沉淀的经验

最后说点我个人写堆排序的体会。老实讲，堆排序是我接触的所有排序算法里，最"反直觉"的一个。快速排序和归并排序的逻辑都比较符合人的分析习惯——分段、递归、合并。但堆排序把数组瞬间想象成一棵完全二叉树，还要通过数组下标来游走父子关系，这个思维转换在初次学习时相当别扭。

我的第一个建议：一定要在纸上走一遍完整的例子。拿一支笔，写出[4, 10, 3, 5, 1]的下标和值，按照sift_down的规则一步步交换。这个过程看起来笨拙，但能帮你建立"数组下标关系"的表象记忆。我敢说，只要完整手动走一遍，你以后再也不会忘记堆排序的核心过程。

第二个建议：单独测试sift_down函数。我在写工程代码时，喜欢把堆化函数独立出来，用一个临时数组手工构造一个"只会破坏堆顶"的场景来测试。例如先建好大顶堆，把堆顶换成很小的值，再调用sift_down，检查调整后的数组是否重新满足堆性质。这样测试能让定位bug更快，而不是每次都要跑完整排序。

第三个建议：理解复杂度不是万能的。很多初学者看到O(n log n)就觉得"很厉害"，但实际工程中常数项和缓存友好度同样重要。今天在Python生态里，几乎没有人会在业务代码里自己写堆排序，因为内置的排序比你手写的更快更稳。这并不代表堆排序不值得学——恰恰相反，sift_down这个操作本身是无数算法的基础，优先队列、TopK、任务调度、外部归并，这些真实场景里都有它的身影。学会堆排序，收获的是对"堆"这种数据结构的深刻理解。

最后分享一个小技巧：如果你在学习过程中始终记不住建堆的起始下标，就用n // 2 - 1这个表达式直接套，然后从大到小往回遍历。不需要死记硬背，只要记住"最后一个非叶子节点"这个定位，你就能推出公式。这样即使换一种语言实现，也不会卡壳。