02.5.2.4 堆排序与工程排序
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.2 排序算法与设计
02.5.2.4-001 堆排序的基本思路是什么?
一句话结论
原地建大顶堆,反复把堆顶最大值换到末尾,剩余堆下沉恢复;升序输出;O(n log n) 时间 O(1) 额外空间,不稳定;堆结构详见 02.4.1.4。
概念解释
- 堆顶最值。
- 交换固定末尾。
- 下沉恢复。
原理流程
- 原地建大顶堆。
- 堆顶换末尾。
- 剩余堆下沉。
代码 / 图示
大顶堆 → 最大在根 → 换末尾 → 下沉
常见误区
- 误区:堆排稳定;正解:跨距交换不稳定。
- 误区:建堆 O(n log n);正解:自底向上建堆 O(n)。
追问
- Q:堆排最坏复杂度? A:O(n log n),不退化。
- Q:额外空间? A:O(1) 原地。
02.5.2.4-002 堆排序怎么实现?
一句话结论
从最后非叶子节点向前下沉建堆;循环把堆顶与当前末尾交换,规模减一,对新堆顶下沉;升序用大顶堆;O(n log n)。
概念解释
- 自底向上建堆。
- 取顶固定。
- 下沉恢复。
原理流程
- 建堆。
- 交换堆顶末尾。
- 下沉堆顶。
代码 / 示例
void heapSort(int[] a) {
int n = a.length;
for (int i = n / 2 - 1; i >= 0; i--) sink(a, i, n);
for (int i = n - 1; i > 0; i--) {
swap(a, 0, i);
sink(a, 0, i);
}
}
void sink(int[] a, int i, int size) {
while (true) {
int l = 2 * i + 1, r = l + 1, best = i;
if (l < size && a[l] > a[best]) best = l;
if (r < size && a[r] > a[best]) best = r;
if (best == i) break;
swap(a, i, best); i = best;
}
}
常见误区
- 误区:建堆从叶子向上逐个插入;正解:自底向上下沉 O(n)。
- 误区:下沉比较孩子大小遗漏;正解:大顶堆选较大孩子。
追问
- Q:降序用什么堆? A:小顶堆,方向对应。
- Q:下沉边界? A:孩子下标 ≥ size 停。
02.5.2.4-003 堆排序复杂度怎么分析?
一句话结论
建堆 O(n);反复取顶 n-1 次,每次下沉 O(log n),排序阶段 O(n log n);总 O(n log n);额外 O(1),递归/迭代下沉均常数辅助;不稳定。
概念解释
- 建堆线性。
- 取顶对数。
- 原地常数。
原理流程
- 建堆 O(n)。
- n-1 次下沉。
- 合计 O(n log n)。
代码 / 图示
建堆 O(n) + (n-1)·O(log n) = O(n log n)
常见误区
- 误区:堆排 O(n) 空间;正解:原地 O(1)。
- 误区:堆排稳定;正解:不稳定。
追问
- Q:为什么工程少用堆排? A:缓存局部性差,常数大于快排。
- Q:最坏退化吗? A:不退化,O(n log n)。
02.5.2.4-004 堆排序与快排、归并怎么对比?
一句话结论
堆排原地 O(1)、最坏 O(n log n) 但不稳定、缓存差;快排常数小但最坏退化、不稳定;归并稳定最坏稳但 O(n) 空间;按空间、稳定、最坏要求权衡。
概念解释
- 空间。
- 稳定性。
- 常数与缓存。
原理流程
- 对比空间。
- 对比稳定与最坏。
- 对比实际常数。
代码 / 图示
堆排:原地 不稳 缓存差
快排:原地 不稳 常数小
归并:O(n) 稳 最坏稳
常见误区
- 误区:堆排综合最优;正解:实际常数与缓存常逊于快排。
- 误区:归并原地;正解:需辅助数组。
追问
- Q:内存受限选谁? A:堆排/快排原地。
- Q:要稳定选谁? A:归并。
02.5.2.4-005 Top-K 堆法怎么选堆方向?
一句话结论
前 K 大用大小 K 小顶堆,堆顶为当前 K 个中最小,便于淘汰;前 K 小用大顶堆;O(n log K) 时间 O(K) 空间;流式数据常驻 K 个。
概念解释
- 堆规模 K。
- 淘汰边界。
- 流式常驻。
原理流程
- 先放 K 个入堆。
- 后续与堆顶比较。
- 更优替换下沉。
代码 / 示例
Queue<Integer> heap = new PriorityQueue<>(); // 小顶堆,前 K 大
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
常见误区
- 误区:前 K 大用大顶堆;正解:小顶堆淘汰最小。
- 误区:堆规模 n;正解:固定 K。
追问
- Q:K 接近 n? A:log K 接近 log n,可直接排序。
- Q:详见哪页? A:02.3.2.4 与 02.4.1.4。
02.5.2.4-006 第 K 大元素(LC 215)堆法怎么做?
一句话结论
小顶堆维护 K 个最大元素,遍历后堆顶即第 K 大;O(n log K) 时间 O(K) 空间;对比快速选择平均 O(n),堆法稳定且适合流式。
概念解释
- K 个候选。
- 堆顶答案。
- 流式可行。
原理流程
- 入堆维护规模 K。
- 超界淘汰堆顶。
- 堆顶返回。
代码 / 示例
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
return heap.peek();
}
常见误区
- 误区:第 K 大用大顶堆取 K 次;正解:小顶堆维护 K 个更省空间。
- 误区:堆空取顶;正解:K ≤ n 保证非空。
追问
- Q:快速选择对比? A:平均 O(n),最坏 O(n²),见 02.5.2.2。
- Q:K=1? A:堆规模 1,即最大值。
02.5.2.4-007 数据流中位数双堆是什么思路?
一句话结论
大顶堆存较小半,小顶堆存较大半;维护两堆规模差 ≤ 1;中位数取堆顶或两堆顶平均;插入 O(log n),查询 O(1);是堆在流式场景的典型应用。
概念解释
- 两半划分。
- 规模平衡。
- 堆顶中位。
原理流程
- 新元素按堆顶关系入堆。
- 调整规模平衡。
- 按规模取中位。
代码 / 图示
大顶堆(小半) | 小顶堆(大半)
常见误区
- 误区:两堆方向反;正解:小半用大顶堆取最大,大半用小顶堆取最小。
- 误区:规模差不控制;正解:差 ≤ 1 保证中位可取。
追问
- Q:LC 295 数据流中位数? A:本框架实现。
- Q:详见哪页? A:02.3.2.4。
02.5.2.4-008 什么是外部排序?
一句话结论
数据量超过内存时,分批读入内存排序后落盘,再多路归并输出;排序过程分内存内排序与磁盘归并两阶段;瓶颈是 I/O 轮次而非 CPU 比较。
概念解释
- 超内存。
- 分批排序。
- 多路归并。
原理流程
- 分块读入排序。
- 块落盘。
- 多路归并输出。
代码 / 图示
大文件 → 内存块排序 → 归并输出
常见误区
- 误区:外部排序一次性载入;正解:分批流式。
- 误区:只优化比较次数;正解:I/O 轮次是主瓶颈。
追问
- Q:适用场景? A:海量日志、大文件排序。
- Q:归并路数受什么限? A:内存可容纳的缓冲区数。
02.5.2.4-009 外部排序分哪几步?
一句话结论
第一步按内存大小切分文件,每块读入用内存排序算法写回临时文件;第二步多路归并,用小顶堆从各有序块取最小输出;必要时多轮归并减少路数。
概念解释
- 生成顺串。
- 多路归并。
- 多轮合并。
原理流程
- 切块排序落盘。
- 堆选各块当前最小。
- 输出并补读。
代码 / 图示
顺串 1 … 顺串 k → 堆归并 → 结果
常见误区
- 误区:归并路数越多越好;正解:受内存缓冲区与 I/O 限制。
- 误区:临时文件无需管理;正解:归并完清理。
追问
- Q:多轮归并为什么需要? A:路数超过内存上限时分层合并。
- Q:顺串是什么? A:内存排好的有序临时块。
02.5.2.4-010 外部排序复杂度怎么算?
一句话结论
设总数据 N、每块可排 M、归并路数 k;生成顺串 O(N log M) 比较;归并轮次 ⌈log_k(N/M)⌉,每轮 I/O 读写 N;主要成本是磁盘 I/O 轮次,CPU 比较次要。
概念解释
- 块规模 M。
- 归并轮次。
- I/O 主导。
原理流程
- 切块排序。
- 按 k 路分层归并。
- 统计 I/O 轮次。
代码 / 图示
轮次 = log_k(顺串数)
常见误区
- 误区:外部排序报 O(n log n) 即可;正解:需列 I/O 轮次。
- 误区:增大 k 无代价;正解:k 受内存缓冲限制。
追问
- Q:怎么减少 I/O? A:增大块、提高归并路数、减少轮次。
- Q:内存排序用什么? A:快排/归并均可。
02.5.2.4-011 多路归并为什么用堆?
一句话结论
K 个有序块各有当前指针,小顶堆存 (值, 块编号),每次取全局最小输出,该块补读下一元素入堆;O(N log K) 比较,避免 K 路两两比较 O(K)。
概念解释
- K 路当前值。
- 堆取最小。
- 补读入堆。
原理流程
- 各块首元素入堆。
- 堆顶输出。
- 同块补读入堆。
代码 / 示例
// 堆元素 (值, 块号);弹出后从对应块补读
常见误区
- 误区:K 路两两比较;正解:堆 O(log K) 选最小。
- 误区:块耗尽未处理;正解:弹出后判块是否读完。
追问
- Q:合并 K 个有序链表? A:同堆思路,见 02.3.1.3。
- Q:堆大小? A:K。
02.5.2.4-012 工程内置排序一般用什么算法?
一句话结论
工程库多为混合排序:小规模插入优化 + 归并/快排主体;对象排序常需稳定,基本类型可用不稳定快排变体;具体算法与阈值随语言版本不同,标注待确认。
概念解释
- 混合优化。
- 稳定需求。
- 版本差异。
原理流程
- 小规模插入。
- 主体分治排序。
- 按类型选稳定与否。
代码 / 图示
插入优化 + 归并/快排混合
常见误区
- 误区:所有语言内置都是快排;正解:对象常用稳定混合排序。
- 误区:阈值与实现跨版本一致;正解:具体版本待确认。
追问
- Q:TimSort 是什么? A:归并 + 插入的稳定混合排序,Python/Java 对象排序等使用(版本细节待确认)。
- Q:双轴快排? A:Java 基本类型排序变体,具体待确认。
02.5.2.4-013 排序稳定性在工程上有什么意义?
一句话结论
多关键字排序时,先按次关键字稳定排序,再按主关键字稳定排序,次关键字次序得以保留;不稳定排序会打乱已排好的次关键字次序。
概念解释
- 多关键字。
- 次序保留。
- 稳定传递。
原理流程
- 先排次关键字。
- 再排主关键字。
- 稳定保次关键字次序。
代码 / 图示
先按班次 → 再按分数(稳定)→ 同分同班次序保留
常见误区
- 误区:单关键字稳定性无所谓;正解:多关键字才体现价值。
- 误区:两次不稳定排序也能保留次序;正解:会被打乱。
追问
- Q:数据库索引排序? A:稳定排序影响等值行次序。
- Q:怎么验证稳定? A:等值带原始下标比对。
02.5.2.4-014 什么情况下不需要全排序?
一句话结论
只取 Top-K、第 K 大、中位数、部分有序输出时,用堆/快速选择/部分排序即可,避免 O(n log n) 全排;全排序仅在需要完整有序序列时必要。
概念解释
- 局部需求。
- 堆/选择。
- 省去全排。
原理流程
- 判断是否需要全序。
- 局部需求选堆/快选。
- 全序才排序。
代码 / 图示
Top-K:堆 O(n log K)
第 K:快选 O(n) 平均
常见误区
- 误区:求第 K 先全排序;正解:堆/快选更省。
- 误区:部分排序后仍需全序;正解:按题目输出范围判断。
追问
- Q:前 K 个有序输出? A:堆维护后再排序 K 个。
- Q:流式 Top-K? A:堆常驻 K。
02.5.2.4-015 堆排序与工程排序有哪些边界用例?
一句话结论
空数组、单元素、已有序、逆序、全相等、K=1、K=n、流式持续输入、超内存大文件;检查堆规模、边界淘汰与外部块划分。
概念解释
- 空与最短。
- 极端输入。
- 流式/超内存。
原理流程
- 空/单点返回。
- K 边界检查。
- 外部切块校验。
代码 / 图示
[] / [1] / 全相等
K=1 / K=n
常见误区
- 误区:K>n 未处理;正解:按题意返回全部或报错。
- 误区:外部排序块大小超内存;正解:按可用内存定 M。
追问
- Q:全相等堆排? A:堆序成立,顺序不保证。
- Q:流式无总量? A:堆常驻,无需全量。
02.5.2.4-016 堆排序与工程排序常见错误有哪些?
一句话结论
建堆方向错、下沉未选较大孩子、Top-K 堆方向反、外部排序一次性载入、多路归并未用堆、稳定性误标;按堆序、淘汰方向、I/O 流程复核。
概念解释
- 堆序维护。
- 淘汰方向。
- 外部流程。
原理流程
- 核对堆类型。
- 核对堆方向。
- 核对归并流程。
代码 / 图示
大顶堆取大 / 小顶堆取小
Top-K:小顶堆淘汰最小
常见误区
- 误区:前 K 大用大顶堆;正解:小顶堆。
- 误区:外部排序忽略 I/O;正解:轮次是主成本。
追问
- Q:怎么自测堆排? A:排完校验升序与堆序。
- Q:多路归并输出重复? A:补读时机核对。
02.5.2.4-017 堆排序与工程排序复杂度怎么汇报?
一句话结论
堆排 O(n log n) 时间 O(1) 空间不稳定;Top-K 堆 O(n log K) O(K);外部排序比较 O(N log M),I/O 轮次 log_k(N/M);双堆中位数插入 O(log n) 查询 O(1)。
概念解释
- 原地堆排。
- 堆规模 K。
- 外部 I/O。
原理流程
- 标注算法与规模。
- 分列比较与 I/O。
- 标注空间。
代码 / 图示
堆排:O(n log n) / O(1)
Top-K:O(n log K) / O(K)
外部:I/O 轮次主导
常见误区
- 误区:外部排序只报比较复杂度;正解:I/O 轮次为主。
- 误区:堆排空间 O(n);正解:原地 O(1)。
追问
- Q:双堆空间? A:O(n) 存全部流式元素。
- Q:堆排缓存问题? A:跨距访问局部性差。
02.5.2.4-018 排序选型总结怎么回答?
一句话结论
小规模/近乎有序:插入;通用内存:快排;要稳定/链表:归并;原地最坏稳:堆排;值域集中:计数;分布均匀:桶;定长拆位:基数;超内存:外部归并;局部 Top-K:堆/快选。
概念解释
- 规模稳定空间。
- 数据分布。
- 局部需求。
原理流程
- 列约束条件。
- 匹配算法性质。
- 给出选型理由。
代码 / 图示
稳定 → 归并/计数/基数
原地 → 快排/堆排
线性 → 非比较(有前提)
常见误区
- 误区:背单一最优算法;正解:按约束权衡。
- 误区:忽略非比较前提;正解:值域/分布假设。
追问
- Q:面试选型题怎么答? A:先问稳定性、空间、数据范围。
- Q:数据特征未知? A:默认快排/归并,再按特征调整。
02.5.2.4-019 堆与排序常见追问有哪些?
一句话结论
堆排为什么不稳定、建堆为什么 O(n)、Top-K 堆方向、外部排序瓶颈、多路归并为什么用堆、工程排序混合策略、稳定性意义;回答围绕堆序维护与场景约束。
概念解释
- 堆性质。
- 工程场景。
- 选型权衡。
原理流程
- 说堆序与下沉。
- 讲场景成本。
- 对比替代。
代码 / 图示
堆序 → 取顶淘汰 → 场景选型
常见误区
- 误区:追问建堆复杂度答 O(n log n);正解:自底向上 O(n)。
- 误区:外部排序瓶颈答 CPU;正解:I/O 轮次。
追问
- Q:堆排与堆结构关系? A:堆是结构,堆排是其应用,见 02.4.1.4。
- Q:Top-K 海量数据? A:分治 + 堆 + 外部归并。
02.5.2.4-020 堆排序与工程排序常见变体有哪些?
一句话结论
手写堆排、Top-K 堆、第 K 大、双堆中位数、外部排序多路归并、合并 K 个有序序列、部分排序、工程混合排序;主线是堆维护最值 + 分治归并,按数据规模与约束选型。
概念解释
- 框架:堆/归并。
- 变体:局部/流式/外部。
- 工程落地。
原理流程
- 判断全序还是局部。
- 选堆/归并/非比较。
- 标注复杂度与空间。
代码 / 图示
最值维护:堆
有序合并:归并
超内存:外部归并
常见误区
- 误区:变体题全排序;正解:局部需求用堆/选择。
- 误区:外部排序套用内存算法;正解:分批 + 归并。
追问
- Q:快速选择见哪页? A:02.5.2.2。
- Q:归并逆序对见哪页? A:02.5.2.3。