InterviewGuide 堆排序实战：从堆原理到 C++ 手撕代码与 Top K 高频考题

• 教程

堆排序（Heapsort）是计算机校招与社招面试中十大排序里出现频率极高的一种排序算法，也是 InterviewGuide 算法模块中明确标注的"非稳定排序重点考察项"（见十大排序总览文档）。本文以阿秀整理的堆排序笔记为骨架，完整继承其中 heapify、heapify_build、heapify_sort 三段核心代码，并结合仓库内面试高频题（实现堆排序、Top K 问题）、LeetCode 题解与 STL 源码剖析，讲透堆排序的底层原理、手撕写法与工程应用，读完即可在笔试面试中直接套用。

一、前置知识：什么是堆，为什么堆能用来排序

堆（Heap）本质上是一种完全二叉树（Complete Binary Tree）：整棵树除了最底层叶节点之外都是填满的，且叶节点从左到右不出现空隙。由于完全二叉树极度紧凑，可以直接用数组（或 C++ 的vector）来存储全部节点——这就是 STL 中所说的"隐式表述法"。

• 若某个节点位于数组下标i处，则其左孩子位于2*i+1，右孩子位于2*i+2，父节点位于(i-1)/2（向下取整）；
• 每个节点的值大于等于其子节点的值，称为大根堆（max heap，大顶堆），此时最大值位于根部；
• 每个节点的值小于等于其子节点的值，称为小根堆（min heap，小顶堆），此时最小值位于根部。

堆排序的基本过程可以概括为三步（这也是面试时《面试高频算法真题》第 7 题给出的标准答案骨架）：

1. 将 n 个元素的序列构建成一个大根堆（或小根堆）；
2. 将堆顶元素（当前最大/最小值）交换到序列末尾；
3. 将前 n-1 个元素重新构建堆，重复上述过程，直到所有元素都有序。

整体时间复杂度为O(n log n)：建堆需要 O(n)，之后每次从堆顶取出元素并重新堆化需要 O(log n)，共执行 n 次。

二、核心三函数手撕堆排序（原笔记完整代码）

阿秀在堆排序笔记中给出的实现由三个函数构成，分工非常清晰，是面试手撕的推荐模板：

1. heapify：对以 i 为根的子树做下沉调整

void heapify(vector<int>& 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(vector<int>& 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，例如 n=8 时该下标为 3；从它开始自下而上对每个节点执行 heapify。之所以要逆序向上，是因为只有先保证子树是大根堆，才能把大值逐层"顶"上去；
• 建堆完成后输出一遍当前数组，便于观察堆形态（此时nums[0]必为全局最大值）。

3. heapify_sort：反复交换堆顶与末尾，逐步收缩堆

void heapify_sort(vector<int>& 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(vector<int>& 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(vector<int>& arr, int len, int index) { int maxid = index; // 计算左右子节点的下标 left=2*i+1 right=2*i+2 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(vector<int>& arr, int len) { // 初次构建堆，i要从最后一个非叶子节点开始，所以是(len-1-1)/2，0这个位置要加等号 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() { vector<int> 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; }

两处易错点（面试官常追问）：

1. 建堆起点必须是最后一个非叶子节点(len-1-1)/2，且循环条件要包含下标 0，否则根节点不参与调整，堆顶不是最大值；
2. 交换堆顶后，adjust 的起点固定是 0（根），传入的堆长度为i（不断缩小），绝不能误写成把i当作 index 传入。

四、从手撕走向 STL：make_heap 四件套与 priority_queue 源码

堆排序的数组形态在 C++ 标准库中有直接对应实现。InterviewGuide 的STL 面试题整理中明确指出：heap 并不是 STL 的容器组件，而是 priority_queue（优先队列）的底层实现机制；binary max heap 的最大值总在根部，因而"优先级最高"。它对外提供四组算法：

• make_heap：把一段数据原地构建成堆（对应上面的heapify_build）；
• push_heap：把位于end()的新元素执行percolate up（上溯）插入堆中；
• pop_heap：把根节点移动到 vector 末尾，再对挤出的元素执行percolate down（下溯），让它从根开始与较大的子节点交换，直至大于左右子节点或下放到叶节点；
• sort_heap：不断执行pop_heap，把当前最大值置于容器末尾并缩小堆范围，最终得到一个递增序列——这与手撕版"交换堆顶 + 缩小堆范围 + 重新堆化"是同一原理。

仓库文档给出了完整实测代码（节选核心）：

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { vector<int> 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 = vector<T>, class Compare = less<typename 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表示默认是大根堆，想要小根堆则用greater<int>。

五、堆排序实战：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_queue<int, vector<int>, greater<int>> 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(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> 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_queue<int, vector<int>, less<int>> big_heap; // 左边一个大顶堆 priority_queue<int, vector<int>, greater<int>> small_heap; // 右边一个小顶堆

5. 最后一块石头的重量

1046. 最后一块石头的重量则用默认的大顶堆模拟"每次取出两块最重的石头"这一贪心过程，priority_queue<int>默认就是大根堆，直接top()/pop()两次、差值非零再push回去即可，代码极其简洁。

6. 有序矩阵中第 K 小的元素

378. 有序矩阵中第K小的元素同样可用"大顶堆求 top 小"：维护一个大小为 K 的大顶堆，堆顶即第 K 小的元素：

priority_queue<int, vector<int>, less<int>> result; // 大顶堆 ... if (result.size() >= k) { if (result.top() > matrix[i][j]) { // 只保留更小的 result.push(matrix[i][j]); result.pop(); } }

六、总结：堆排序的复杂度画像与面试要点

面试高频追问点可归纳为三条：一是"为什么建堆要从最后一个非叶子节点(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：最后一块石头的重量（大顶堆贪心）

• 教程