企业官网建设流程全解析

OI-wiki 堆排序（Heapsort）全解：基于二叉堆的原地选择排序与数组实现

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

本篇文章以 OI-wiki 的 堆排序文档 为主体，系统讲解堆排序的定义、排序过程、在数组上建立二叉堆的下标关系、复杂度与稳定性等核心性质，并给出 C++ 与 Python 的完整可运行实现。同时结合仓库中 二叉堆 的源码级细节（向上/向下调整、$O(n)$ 建堆、对顶堆应用）进行纵深拓展，帮助你不仅会背代码，更能理解"为什么堆排序是最坏情况也是 $O(n\log n)$ 的原地比较排序"。

定义

堆排序（英语：Heapsort）是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组——这正是它的优势所在：不依赖链表等额外结构，可以直接在待排序的数组上完成建堆与排序。

在深入堆排序之前，需要先明确二叉堆的两条基本事实（详见 二叉堆 的"结构"一节）：

• 二叉堆是一棵完全二叉树，每个结点中存有一个元素（权值）；
• 堆性质：父亲的权值不小于儿子的权值（大根堆）。由此可知，树根存的是当前堆中的最大值。

堆排序正是建立在这两个性质之上的。

过程

堆排序的本质是建立在堆上的选择排序——它与 选择排序 一样，每轮"选出当前最大/最小的元素放到最终位置"，区别只在于：选择排序每次线性扫描找极值（$O(n)$），而堆排序通过堆把"找极值"优化到了 $O(\log n)$。

排序（反复取堆顶）

以大根堆为例，排序过程如下：

1. 首先建立大顶堆，此时堆顶元素即为整个数组的最大值；
2. 将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质（对新的堆顶做向下调整）；
3. 之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；
4. 以此类推，在第 $n-1$ 次操作后，整个数组就完成了排序。

也就是说：每轮操作都把当前堆中的最大值"沉淀"到数组末尾，堆的规模逐渐缩小，数组末尾的已排序区逐渐增长，直至全部排好。

在数组上建立二叉堆

从根节点开始，依次将每一层的节点排列在数组里。由于完全二叉树的结构特性，可以完全用数组下标定位父子关系，而不需要存储任何指针。于是有数组中下标为i的节点，对应的父结点、左子结点和右子结点如下：

iParent(i) = (i - 1) / 2; iLeftChild(i) = 2 * i + 1; iRightChild(i) = 2 * i + 2;

以仓库中的示意图 二叉堆的数组存储 为例，可以直观看到这棵完全二叉树是如何按层序铺满数组的。

注：图中采用 1 基下标（$h_i$ 的两个儿子为 $h_{2i}$ 和 $h_{2i+1}$），而堆排序文档的示例代码采用 0 基下标，因此出现2*i+1、2*i+2的形式。两种约定本质等价，理解其一即可互相推导。

维持堆性质的核心操作：向下调整（sift down）

堆排序的整个"取堆顶—交换—恢复堆性质"循环，唯一反复使用的原语就是向下调整。在 二叉堆 的"删除操作"一节中给出了它的定义：

在该结点的儿子中，找一个最大的，与该结点交换，重复此过程直到底层。

可以证明，删除根结点（等价于用最后一个元素顶替根）并向下调整后，没有其他结点会不满足堆性质，时间复杂度为 $O(\log n)$。

性质

稳定性

不稳定。

同选择排序一样，由于堆排序中包含交换位置的操作（堆顶元素与数组末尾元素交换、父子结点的交换），相等的元素在排序后相对顺序可能发生改变。

关于"稳定性"的正式定义与稳定排序家族，可参考 排序简介 的"稳定性"一节：稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。在该文档中，堆排序与选择排序、快速排序、希尔排序被明确归为不稳定排序，而基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

另外值得一提的是，数组实现的选择排序因依赖swap操作而不稳定（详见 选择排序 的性质一节）；堆排序的"交换"同样是从根本结构上引入的，因此无法像链表实现的选择排序那样通过改写实现方式挽回稳定性。

时间复杂度

堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为$O(n\log n)$。

这是堆排序最突出的卖点之一：绝大多数 $O(n\log n)$ 排序（如 快速排序）最坏情况会退化，而堆排序的复杂度上下界完全一致，不存在退化到 $O(n^2)$ 的可能。同时，根据 排序简介 中的结论，基于比较的排序算法的时间复杂度下限就是 $O(n\log n)$，因此堆排序在渐近意义上已经是"最优档位"之一。

时间开销的构成可以拆解如下：

• 建堆：从最后一个内部结点开始逐个向下调整，总代价为 $O(n)$（而非直觉上的 $O(n\log n)$，原因见下文"建堆"小节）；
• 排序：共 $n-1$ 轮，每轮进行一次交换 + 一次 $O(\log n)$ 的向下调整，合计 $O(n\log n)$。

两者相加仍为 $O(n\log n)$。

空间复杂度

$O(1)$，且为原地算法（in-place）。

由于可以直接在输入数组上建立堆（数组本身就是那棵完全二叉树的层序存储），不需要申请额外的 $O(n)$ 空间来存放堆结构，所有操作都在原数组内完成，因此空间复杂度为常数级。这一点优于归并排序等需要额外辅助空间的 $O(n\log n)$ 排序。

建堆：为什么能 $O(n)$ 完成

堆排序的第一步是在数组上建堆。直观想法是从空堆开始逐个插入，那样需要 $O(n\log n)$。而 二叉堆 的"建堆"一节给出了两种方法：

• 方法一：向上调整（BFS 序）——从根开始依次up(i)，这仍然相当于一个一个插入，只是把元素提前放在了数组里，可以改善常数，但最坏情况下递推式为 $T(n) = T(n - 1) + \Theta(\log n)$，累加得 $T(n) = \Theta(n\log n)$；
• 方法二：向下调整——从叶子方向开始，逐个向下调整。每次相当于"合并两个已经调整好的堆"，叶节点无需调整，因此可以从序列约 $n/2$ 的位置开始调整，递推式 $T(n) = 2T(\dfrac{n}{2}) + O(\log n)$，由主定理可得 $T(n) = \Theta(n)$。

堆排序文档中heap_sort的堆化循环for (int i = (len - 1 - 1) / 2; i >= 0; i--)正是从最后一个结点的父节点开始逆序向下调整，即方法二的 0 基下标版本。

之所以能 $\Theta(n)$ 建堆，深层原因是堆性质很弱，二叉堆并不是唯一的——对同样一组数据，只要满足"父亲不小于儿子"即可，内部结构可以有多种形态，因此不必像排序那样付出强条件的代价。

实现

堆排序的实现由两个函数构成：sift_down（向下调整，堆排序的核心原语）与heap_sort（堆化 + 反复取堆顶）。仓库文档同时提供了 C++ 与 Python 两种语言的完整实现，此处完整给出并逐段注释。

C++

void sift_down(int arr[], int start, int end) { // 计算父结点和子结点的下标 int parent = start; int child = parent * 2 + 1; while (child <= end) { // 子结点下标在范围内才做比较 // 先比较两个子结点大小，选择最大的 if (child + 1 <= end && arr[child] < arr[child + 1]) child++; // 如果父结点比子结点大，代表调整完毕，直接跳出函数 if (arr[parent] >= arr[child]) return; else { // 否则交换父子内容，子结点再和孙结点比较 swap(arr[parent], arr[child]); parent = child; child = parent * 2 + 1; } } } void heap_sort(int arr[], int len) { // 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify) for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1); // 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); sift_down(arr, 0, i - 1); } }

Python

def sift_down(arr, start, end): # 计算父结点和子结点的下标 parent = int(start) child = int(parent * 2 + 1) while child <= end: # 子结点下标在范围内才做比较 # 先比较两个子结点大小，选择最大的 if child + 1 <= end and arr[child] < arr[child + 1]: child += 1 # 如果父结点比子结点大，代表调整完毕，直接跳出函数 if arr[parent] >= arr[child]: return else: # 否则交换父子内容，子结点再和孙结点比较 arr[parent], arr[child] = arr[child], arr[parent] parent = child child = int(parent * 2 + 1) def heap_sort(arr, len): # 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify) i = (len - 1 - 1) / 2 while i >= 0: sift_down(arr, i, len - 1) i -= 1 # 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕 i = len - 1 while i > 0: arr[0], arr[i] = arr[i], arr[0] sift_down(arr, 0, i - 1) i -= 1

实现要点解读

对照 二叉堆 中的参考代码down函数：

void down(int x) { while (x * 2 <= n) { t = x * 2; if (t + 1 <= n && h[t + 1] > h[t]) t++; if (h[t] <= h[x]) break; std::swap(h[x], h[t]); x = t; } }

可以确认二者是同一原语的不同下标约定：down用 1 基下标、在"儿子权值不大于父亲时break"，sift_down用 0 基下标、在"父结点不小于最大子结点时return"。理解这点后，在任何下标体系下都能写出正确的向下调整。

几个值得注意的实现细节：

• sift_down的第一处if负责在左右两个儿子中选出较大的那个（先假设左儿子更大，若右儿子存在且更大则切换到右儿子）；
• 第二处if是提前终止条件：父结点已不小于最大子结点时堆性质已恢复，无需继续下沉；
• 排序循环中swap(arr[0], arr[i])把当前最大值放到数组末尾的已排序区，随后sift_down(arr, 0, i - 1)只在尚未排序的前缀上恢复堆性质——这也对应了空间复杂度 $O(1)$ 的原地特性；
• 堆化循环i = (len - 1 - 1) / 2是"最后一个结点的父节点"：最后一个结点下标为len-1，其父节点为(len-1-1)/2。从它开始逆序向前调整，就是前面推导的 $O(n)$ 建堆方法。

排序的用途与堆的实际应用场景

堆排序在 OI 中直接使用的频率不高——库函数排序（C++ 的std::sort、STL 中的排序）通常常数更小、实现更稳，但当需要稳定 $O(n\log n)$ + $O(1)$ 额外空间、或需要把"堆"这种数据结构作为中间步骤时，理解堆排序的价值就体现出来了。排序本身作为一种预处理手段的价值，可参考 排序的用法：排序有助于理解数据特点、降低后续处理的时间复杂度、并作为 二分查找 的预处理。

堆排序背后真正值得反复使用的是二叉堆数据结构本身。仓库在 二叉堆 的"应用"一节给出了一个经典实例——对顶堆（一个维护前 $k$ 大的小根堆 + 一个维护其余小值的大根堆），用于动态维护第 $k$ 大的数：查询第 $k$ 大是 $O(1)$，插入、删除与调整 $k$ 值均为 $O(\log n)$。对应的完整参考实现位于 docs/ds/code/binary-heap/binary-heap_1.cpp，其中大根堆用priority_queue<int, vector<int>, less<int>>、小根堆用greater<int>实现，并有配套的 输入样例 与 标准输出 可用于验证程序正确性。

小结

堆排序以"建堆 $O(n)$ + 每轮取堆顶 $O(\log n)$"的组合，用数组这一最朴素的数据结构达成了最坏情况 $O(n\log n)$ 的比较排序下界，同时保持了 $O(1)$ 的空间占用。掌握其下标映射、向下调整与建堆复杂度分析，是理解 二叉堆 及其各类应用（优先队列、对顶堆、堆优化的 Dijkstra 等）的基础，值得仔细推敲每一行代码背后的堆性质。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki