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)$。排序反复取堆顶以大根堆为例排序过程如下首先建立大顶堆此时堆顶元素即为整个数组的最大值将堆顶的元素取出作为最大值与数组尾部的元素交换并维持残余堆的性质对新的堆顶做向下调整之后将堆顶的元素取出作为次大值与数组倒数第二位元素交换并维持残余堆的性质以此类推在第 $n-1$ 次操作后整个数组就完成了排序。也就是说每轮操作都把当前堆中的最大值沉淀到数组末尾堆的规模逐渐缩小数组末尾的已排序区逐渐增长直至全部排好。在数组上建立二叉堆从根节点开始依次将每一层的节点排列在数组里。由于完全二叉树的结构特性可以完全用数组下标定位父子关系而不需要存储任何指针。于是有数组中下标为i的节点对应的父结点、左子结点和右子结点如下iParent(i) (i - 1) / 2; iLeftChild(i) 2 * i 1; iRightChild(i) 2 * i 2;以仓库中的示意图 二叉堆的数组存储 为例可以直观看到这棵完全二叉树是如何按层序铺满数组的。注图中采用 1 基下标$h_i$ 的两个儿子为 $h_{2i}$ 和 $h_{2i1}$而堆排序文档的示例代码采用 0 基下标因此出现2*i1、2*i2的形式。两种约定本质等价理解其一即可互相推导。维持堆性质的核心操作向下调整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 两种语言的完整实现此处完整给出并逐段注释。Cvoid 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); } }Pythondef 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 基下标、在儿子权值不大于父亲时breaksift_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_queueint, vectorint, lessint、小根堆用greaterint实现并有配套的 输入样例 与 标准输出 可用于验证程序正确性。小结性质结论算法类型基于比较的排序建立在堆上的选择排序稳定性不稳定源于交换操作最优 / 平均 / 最坏时间复杂度均为 $O(n\log n)$空间复杂度$O(1)$原地算法适用数据结构数组层序存储完全二叉树核心原语向下调整sift down堆排序以建堆 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 堆排序（Heapsort）全解：基于二叉堆的原地选择排序与数组实现
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)$。排序反复取堆顶以大根堆为例排序过程如下首先建立大顶堆此时堆顶元素即为整个数组的最大值将堆顶的元素取出作为最大值与数组尾部的元素交换并维持残余堆的性质对新的堆顶做向下调整之后将堆顶的元素取出作为次大值与数组倒数第二位元素交换并维持残余堆的性质以此类推在第 $n-1$ 次操作后整个数组就完成了排序。也就是说每轮操作都把当前堆中的最大值沉淀到数组末尾堆的规模逐渐缩小数组末尾的已排序区逐渐增长直至全部排好。在数组上建立二叉堆从根节点开始依次将每一层的节点排列在数组里。由于完全二叉树的结构特性可以完全用数组下标定位父子关系而不需要存储任何指针。于是有数组中下标为i的节点对应的父结点、左子结点和右子结点如下iParent(i) (i - 1) / 2; iLeftChild(i) 2 * i 1; iRightChild(i) 2 * i 2;以仓库中的示意图 二叉堆的数组存储 为例可以直观看到这棵完全二叉树是如何按层序铺满数组的。注图中采用 1 基下标$h_i$ 的两个儿子为 $h_{2i}$ 和 $h_{2i1}$而堆排序文档的示例代码采用 0 基下标因此出现2*i1、2*i2的形式。两种约定本质等价理解其一即可互相推导。维持堆性质的核心操作向下调整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 两种语言的完整实现此处完整给出并逐段注释。Cvoid 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); } }Pythondef 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 基下标、在儿子权值不大于父亲时breaksift_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_queueint, vectorint, lessint、小根堆用greaterint实现并有配套的 输入样例 与 标准输出 可用于验证程序正确性。小结性质结论算法类型基于比较的排序建立在堆上的选择排序稳定性不稳定源于交换操作最优 / 平均 / 最坏时间复杂度均为 $O(n\log n)$空间复杂度$O(1)$原地算法适用数据结构数组层序存储完全二叉树核心原语向下调整sift down堆排序以建堆 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考