教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载堆排序Heapsort是计算机校招与社招面试中十大排序里出现频率极高的一种排序算法也是 InterviewGuide 算法模块中明确标注的非稳定排序重点考察项见十大排序总览文档。本文以阿秀整理的堆排序笔记为骨架完整继承其中 heapify、heapify_build、heapify_sort 三段核心代码并结合仓库内面试高频题实现堆排序、Top K 问题、LeetCode 题解与 STL 源码剖析讲透堆排序的底层原理、手撕写法与工程应用读完即可在笔试面试中直接套用。一、前置知识什么是堆为什么堆能用来排序堆Heap本质上是一种完全二叉树Complete Binary Tree整棵树除了最底层叶节点之外都是填满的且叶节点从左到右不出现空隙。由于完全二叉树极度紧凑可以直接用数组或 C 的vector来存储全部节点——这就是 STL 中所说的隐式表述法。若某个节点位于数组下标i处则其左孩子位于2*i1右孩子位于2*i2父节点位于(i-1)/2向下取整每个节点的值大于等于其子节点的值称为大根堆max heap大顶堆此时最大值位于根部每个节点的值小于等于其子节点的值称为小根堆min heap小顶堆此时最小值位于根部。堆排序的基本过程可以概括为三步这也是面试时《面试高频算法真题》第 7 题给出的标准答案骨架将 n 个元素的序列构建成一个大根堆或小根堆将堆顶元素当前最大/最小值交换到序列末尾将前 n-1 个元素重新构建堆重复上述过程直到所有元素都有序。整体时间复杂度为O(n log n)建堆需要 O(n)之后每次从堆顶取出元素并重新堆化需要 O(log n)共执行 n 次。二、核心三函数手撕堆排序原笔记完整代码阿秀在堆排序笔记中给出的实现由三个函数构成分工非常清晰是面试手撕的推荐模板1. heapify对以 i 为根的子树做下沉调整void heapify(vectorint nums, int n, int i) // 对有一定顺序的堆 // 当前第i个结点取根左右的最大值这个操作称heapify { int l i * 2 1, r i * 2 2; int max i; if (l n nums[l] nums[max]) max l; if (r n nums[r] nums[max]) max r; if (max ! i) { swap(nums[max], nums[i]); heapify(nums, n, max); // 递归向下调整被换下来的节点 } }关键点解析通过l i * 2 1、r i * 2 2计算左右孩子下标这是完全二叉树数组表示的核心在根、左、右三者中选出最大值所在下标max若最大值不是根则交换根与最大值节点并递归对max位置继续 heapify保证子树整体满足大根堆性质边界条件l n、r n确保不越界因为完全二叉树中下标超过 n 的孩子视为不存在。2. heapify_build从倒数第二层向上建堆void heapify_build(vectorint nums, int n) // 建立大根堆从树的倒数第二层第一个结点开始 // 对每个结点进行heapify操作然后向上走 { int temp (n - 2) / 2; // 最后一个非叶子节点的下标 for (int i temp; i 0; i--) heapify(nums, n, i); for (int i 0; i nums.size(); i) cout nums[i] ; cout endl; }关键点解析最后一个非叶子节点下标为(n-2)/2例如 n8 时该下标为 3从它开始自下而上对每个节点执行 heapify。之所以要逆序向上是因为只有先保证子树是大根堆才能把大值逐层顶上去建堆完成后输出一遍当前数组便于观察堆形态此时nums[0]必为全局最大值。3. heapify_sort反复交换堆顶与末尾逐步收缩堆void heapify_sort(vectorint nums, int n) // 建立大根堆之后每次交换最后一个结点和根节点最大值 // 对交换后的根节点继续进行heapify此时堆的最后一位是最大值因此不用管他n变为n-1 { heapify_build(nums, n); for (int i 0; i n; i) { swap(nums.front(), nums[n - i - 1]); // 堆顶最大值放到当前堆的末尾 heapify(nums, n - i - 1, 0); // 堆规模减一从根重新下沉调整 } }关键点解析先建堆之后循环 n 次把堆顶最大值与当前堆范围的最后一个元素交换然后对缩小后的堆范围n-i-1从根节点0重新 heapify由于最大值已被冻结在末尾heapify 的范围每次减一最终得到一个递增序列整个排序过程只借助swap在原数组上完成空间复杂度 O(1)是原地排序但因为相同元素可能在交换堆顶与末尾时发生相对位置改变堆排序是不稳定的——这一点与算法基础文档中堆排序属于非稳定排序、面试常被问的结论一致。三、面试手撕版本一次 swap 都不要多余的高频答案在《面试高频算法真题》第 7 题实现一个堆排序中阿秀给出了另一个面试常用写法结构与上面的三函数版等价但做了两处细节处理用异或实现 swap、把建堆与排序合并进一个heapsort#include iostream #include vector using namespace std; void swap(vectorint arr, int a, int b) { arr[a] arr[a] ^ arr[b]; arr[b] arr[a] ^ arr[b]; arr[a] arr[a] ^ arr[b]; } void adjust(vectorint arr, int len, int index) { int maxid index; // 计算左右子节点的下标 left2*i1 right2*i2 parent(i-1)/2 int left 2 * index 1, right 2 * index 2; // 寻找当前以index为根的子树中最大元素的的下标 if (left len arr[left] arr[maxid]) maxid left; if (right len arr[right] arr[maxid]) maxid right; // 进行交换记得要递归进行adjust传入的index是maxid if (maxid ! index) { swap(arr, maxid, index); adjust(arr, len, maxid); } } void heapsort(vectorint arr, int len) { // 初次构建堆i要从最后一个非叶子节点开始所以是(len-1-1)/20这个位置要加等号 for (int i (len - 1 - 1) / 2; i 0; i--) { adjust(arr, len, i); } // 从最后一个元素的下标开始往前遍历每次将堆顶元素交换至当前位置并且缩小长度i为长度从0处开始adjust for (int i len - 1; i 0; i--) { swap(arr, 0, i); adjust(arr, i, 0); // 注意每次adjust是从根往下调整所以这里index是0 } } int main() { vectorint arr { 3,4,2,1,5,8,7,6 }; cout before: endl; for (int item : arr) cout item ; cout endl; heapsort(arr, arr.size()); cout after: endl; for (int item : arr) cout item ; cout endl; return 0; }两处易错点面试官常追问建堆起点必须是最后一个非叶子节点(len-1-1)/2且循环条件要包含下标 0否则根节点不参与调整堆顶不是最大值交换堆顶后adjust 的起点固定是 0根传入的堆长度为i不断缩小绝不能误写成把i当作 index 传入。四、从手撕走向 STLmake_heap 四件套与 priority_queue 源码堆排序的数组形态在 C 标准库中有直接对应实现。InterviewGuide 的STL 面试题整理中明确指出heap 并不是 STL 的容器组件而是 priority_queue优先队列的底层实现机制binary max heap 的最大值总在根部因而优先级最高。它对外提供四组算法make_heap把一段数据原地构建成堆对应上面的heapify_buildpush_heap把位于end()的新元素执行percolate up上溯插入堆中pop_heap把根节点移动到 vector 末尾再对挤出的元素执行percolate down下溯让它从根开始与较大的子节点交换直至大于左右子节点或下放到叶节点sort_heap不断执行pop_heap把当前最大值置于容器末尾并缩小堆范围最终得到一个递增序列——这与手撕版交换堆顶 缩小堆范围 重新堆化是同一原理。仓库文档给出了完整实测代码节选核心#include iostream #include algorithm #include vector using namespace std; int main() { vectorint v { 0,1,2,3,4,5,6 }; make_heap(v.begin(), v.end()); // 以vector为底层容器 for (auto i : v) cout i ; // 6 4 5 3 1 0 2 cout endl; v.push_back(7); push_heap(v.begin(), v.end()); for (auto i : v) cout i ; // 7 6 5 4 1 0 2 3 cout endl; pop_heap(v.begin(), v.end()); cout v.back() endl; // 7 v.pop_back(); for (auto i : v) cout i ; // 6 4 5 3 1 0 2 cout endl; sort_heap(v.begin(), v.end()); for (auto i : v) cout i ; // 0 1 2 3 4 5 6 return 0; }而priority_queue之所以是容器配接器而非容器正是因为它以vector为底层容器、以 heap 算法为处理规则且只允许取用堆顶元素、不提供迭代器。文档中给出的核心源码骨架如下template class T, class Sequence vectorT, class Compare lesstypename Sequence::value_type class priority_queue{ ... protected: Sequence c; // 底层容器 Compare comp; // 元素大小比较标准 public: bool empty() const { return c.empty(); } size_type size() const { return c.size(); } const_reference top() const { return c.front(); } void push(const value_type x) { c.push_back(x); push_heap(c.begin(), c.end(), comp); } void pop() { pop_heap(c.begin(), c.end(), comp); c.pop_back(); } };可见push内部就是尾插 push_heap 上溯pop内部就是pop_heap 下溯 pop_back与手撕 heapify 完全同构。默认Compare less表示默认是大根堆想要小根堆则用greaterint。五、堆排序实战Top K、数据流中位数与高频元素堆排序在面试中的价值远超排个序本身几乎所有求前 K 大/前 K 小的问题都以大小为 K 的堆为最优解InterviewGuide 的题库中就有多处直接应用1. Top K 问题最大堆/最小堆 priority_queue《面试高频算法真题》第 12 题Top K 问题给出的核心结论是使用最大最小堆。求最大的数用最小堆求最小的数用最大堆。以 top K 最大元素为例按顺序扫描 N 个数先取 K 个元素构建一个大小为 K 的最小堆每扫到一个元素若大于堆顶当前堆中最小的数则插入并删除堆顶同时整理堆若小于堆顶则直接丢弃。最后堆中剩下的就是最大的前 K 个元素堆顶就是第 K 大的元素。插入的复杂度为 O(log K)初始化建堆为 O(K log K)。C 中对应实现即标准库priority_queue例如剑指 Offer No29最小的 K 个数就用最小堆不断取堆顶得到最小的 K 个数priority_queueint, vectorint, greaterint pq; // 小顶堆 for (auto a : input) pq.push(a); while (k--) { result.push_back(pq.top()); pq.pop(); }2. LeetCode 215数组中第 K 个最大元素经典高频215. 数组中的第K个最大元素给出的最优解就是小顶堆维护前 K 大堆容量恒为 K返回堆顶即为第 K 大的元素int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint res; // 小顶堆 for (auto a : nums) { res.push(a); if (res.size() k) res.pop(); // 始终保持堆内为最大的k个元素 } return res.top(); }3. 前 K 个高频元素 / 高频单词347. 前 K 个高频元素与692. 前 K 个高频单词的思路完全一致先用unordered_map统计频率再维护一个大小为 K 的堆堆内按频率排序自定义compare仿函数超出容量即弹出堆顶最后逆序输出。题解中还特别强调了一句面试红线求前 k 大用小根堆求前 k 小用大根堆。面试的时候如果说反了会挂4. 数据流中位数双堆经典结构剑指 Offer No63数据流中的中位数把堆的应用推向更复杂形态维护左边一个大顶堆 右边一个小顶堆保证左堆所有元素 ≤ 右堆所有元素且两堆大小之差不超过 1则中位数要么是大顶堆堆顶要么是两个堆顶的平均值priority_queueint, vectorint, lessint big_heap; // 左边一个大顶堆 priority_queueint, vectorint, greaterint small_heap; // 右边一个小顶堆5. 最后一块石头的重量1046. 最后一块石头的重量则用默认的大顶堆模拟每次取出两块最重的石头这一贪心过程priority_queueint默认就是大根堆直接top()/pop()两次、差值非零再push回去即可代码极其简洁。6. 有序矩阵中第 K 小的元素378. 有序矩阵中第K小的元素同样可用大顶堆求 top 小维护一个大小为 K 的大顶堆堆顶即第 K 小的元素priority_queueint, vectorint, lessint result; // 大顶堆 ... if (result.size() k) { if (result.top() matrix[i][j]) { // 只保留更小的 result.push(matrix[i][j]); result.pop(); } }六、总结堆排序的复杂度画像与面试要点维度结论平均时间复杂度O(n log n)最坏时间复杂度O(n log n)不像快排会退化为 O(n²)空间复杂度O(1)原地排序稳定性不稳定交换堆顶与末尾可能改变相等元素的相对顺序适用场景大数据量的 Top K、优先队列、流式数据中位数、高频元素面试高频追问点可归纳为三条一是为什么建堆要从最后一个非叶子节点(n-2)/2开始自下而上二是为什么排序阶段每次 heapify 的堆长度要减一三是求前 K 大用小根堆、求前 K 小用大根堆这一 Top K 心法。手撕时优先使用本文第二节的三函数版heapify / heapify_build / heapify_sort它与 STL 的 make_heap / sort_heap 语义一一对应若追求精简则直接背诵第三节的heapsort面试版。参考资料本仓库内延伸阅读堆排序笔记本文主体含完整三函数代码十大排序合集堆排序完整版与视频讲解算法基础稳定排序/原地排序概念与十大排序复杂度总览面试高频算法真题实现堆排序与 Top K 问题STL 面试题heap 四算法与 priority_queue 源码LeetCode 215数组中的第 K 个最大元素LeetCode 347前 K 个高频元素剑指 Offer No29最小的 K 个数剑指 Offer No63数据流中的中位数双堆LeetCode 1046最后一块石头的重量大顶堆贪心赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐692. 前 K 个高频单词哈希表统计 堆/排序的 Top K 经典解法InterviewGuide 力扣刷题笔记692. 前 K 个高频单词哈希表统计 堆/排序的 Top K 经典解法InterviewGuide 力扣刷题笔记 本文是《InterviewGuid文档教程知识库前 K 个高频元素Top K Frequent Elements排序、最小堆与桶排序三种解法全解析前 K 个高频元素Top K Frequent Elements排序、最小堆与桶排序三种解法全解析 导读 本文以 LeetCode 347「前 K 个高频示例工程教程堆排序原理与 C 实现详解InterviewGuide 十大排序算法系列第 7 篇堆排序原理与 C 实现详解InterviewGuide 十大排序算法系列第 7 篇 堆排序Heap Sort是《InterviewGuide》 十文档教程知识库上一篇Wand-Enhancer终极指南3分钟免费解锁WeMod Pro完整功能下一篇终极防撤回解决方案RevokeMsgPatcher完整使用指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考