罗罗编程学习记录
本页内容 展开查看

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。

概念解释

  • 堆顶最值。
  • 交换固定末尾。
  • 下沉恢复。

原理流程

  1. 原地建大顶堆。
  2. 堆顶换末尾。
  3. 剩余堆下沉。

代码 / 图示

大顶堆 → 最大在根 → 换末尾 → 下沉

常见误区

  • 误区:堆排稳定;正解:跨距交换不稳定。
  • 误区:建堆 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)。

概念解释

  • 自底向上建堆。
  • 取顶固定。
  • 下沉恢复。

原理流程

  1. 建堆。
  2. 交换堆顶末尾。
  3. 下沉堆顶。

代码 / 示例

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),递归/迭代下沉均常数辅助;不稳定。

概念解释

  • 建堆线性。
  • 取顶对数。
  • 原地常数。

原理流程

  1. 建堆 O(n)。
  2. n-1 次下沉。
  3. 合计 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) 空间;按空间、稳定、最坏要求权衡。

概念解释

  • 空间。
  • 稳定性。
  • 常数与缓存。

原理流程

  1. 对比空间。
  2. 对比稳定与最坏。
  3. 对比实际常数。

代码 / 图示

堆排:原地 不稳 缓存差
快排:原地 不稳 常数小
归并: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。
  • 淘汰边界。
  • 流式常驻。

原理流程

  1. 先放 K 个入堆。
  2. 后续与堆顶比较。
  3. 更优替换下沉。

代码 / 示例

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 个候选。
  • 堆顶答案。
  • 流式可行。

原理流程

  1. 入堆维护规模 K。
  2. 超界淘汰堆顶。
  3. 堆顶返回。

代码 / 示例

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. 新元素按堆顶关系入堆。
  2. 调整规模平衡。
  3. 按规模取中位。

代码 / 图示

大顶堆(小半) | 小顶堆(大半)

常见误区

  • 误区:两堆方向反;正解:小半用大顶堆取最大,大半用小顶堆取最小。
  • 误区:规模差不控制;正解:差 ≤ 1 保证中位可取。

追问

  • Q:LC 295 数据流中位数? A:本框架实现。
  • Q:详见哪页? A:02.3.2.4。

02.5.2.4-008 什么是外部排序?

一句话结论

数据量超过内存时,分批读入内存排序后落盘,再多路归并输出;排序过程分内存内排序与磁盘归并两阶段;瓶颈是 I/O 轮次而非 CPU 比较。

概念解释

  • 超内存。
  • 分批排序。
  • 多路归并。

原理流程

  1. 分块读入排序。
  2. 块落盘。
  3. 多路归并输出。

代码 / 图示

大文件 → 内存块排序 → 归并输出

常见误区

  • 误区:外部排序一次性载入;正解:分批流式。
  • 误区:只优化比较次数;正解:I/O 轮次是主瓶颈。

追问

  • Q:适用场景? A:海量日志、大文件排序。
  • Q:归并路数受什么限? A:内存可容纳的缓冲区数。

02.5.2.4-009 外部排序分哪几步?

一句话结论

第一步按内存大小切分文件,每块读入用内存排序算法写回临时文件;第二步多路归并,用小顶堆从各有序块取最小输出;必要时多轮归并减少路数。

概念解释

  • 生成顺串。
  • 多路归并。
  • 多轮合并。

原理流程

  1. 切块排序落盘。
  2. 堆选各块当前最小。
  3. 输出并补读。

代码 / 图示

顺串 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 主导。

原理流程

  1. 切块排序。
  2. 按 k 路分层归并。
  3. 统计 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 路当前值。
  • 堆取最小。
  • 补读入堆。

原理流程

  1. 各块首元素入堆。
  2. 堆顶输出。
  3. 同块补读入堆。

代码 / 示例

// 堆元素 (值, 块号);弹出后从对应块补读

常见误区

  • 误区:K 路两两比较;正解:堆 O(log K) 选最小。
  • 误区:块耗尽未处理;正解:弹出后判块是否读完。

追问

  • Q:合并 K 个有序链表? A:同堆思路,见 02.3.1.3。
  • Q:堆大小? A:K。

02.5.2.4-012 工程内置排序一般用什么算法?

一句话结论

工程库多为混合排序:小规模插入优化 + 归并/快排主体;对象排序常需稳定,基本类型可用不稳定快排变体;具体算法与阈值随语言版本不同,标注待确认。

概念解释

  • 混合优化。
  • 稳定需求。
  • 版本差异。

原理流程

  1. 小规模插入。
  2. 主体分治排序。
  3. 按类型选稳定与否。

代码 / 图示

插入优化 + 归并/快排混合

常见误区

  • 误区:所有语言内置都是快排;正解:对象常用稳定混合排序。
  • 误区:阈值与实现跨版本一致;正解:具体版本待确认。

追问

  • Q:TimSort 是什么? A:归并 + 插入的稳定混合排序,Python/Java 对象排序等使用(版本细节待确认)。
  • Q:双轴快排? A:Java 基本类型排序变体,具体待确认。

02.5.2.4-013 排序稳定性在工程上有什么意义?

一句话结论

多关键字排序时,先按次关键字稳定排序,再按主关键字稳定排序,次关键字次序得以保留;不稳定排序会打乱已排好的次关键字次序。

概念解释

  • 多关键字。
  • 次序保留。
  • 稳定传递。

原理流程

  1. 先排次关键字。
  2. 再排主关键字。
  3. 稳定保次关键字次序。

代码 / 图示

先按班次 → 再按分数(稳定)→ 同分同班次序保留

常见误区

  • 误区:单关键字稳定性无所谓;正解:多关键字才体现价值。
  • 误区:两次不稳定排序也能保留次序;正解:会被打乱。

追问

  • Q:数据库索引排序? A:稳定排序影响等值行次序。
  • Q:怎么验证稳定? A:等值带原始下标比对。

02.5.2.4-014 什么情况下不需要全排序?

一句话结论

只取 Top-K、第 K 大、中位数、部分有序输出时,用堆/快速选择/部分排序即可,避免 O(n log n) 全排;全排序仅在需要完整有序序列时必要。

概念解释

  • 局部需求。
  • 堆/选择。
  • 省去全排。

原理流程

  1. 判断是否需要全序。
  2. 局部需求选堆/快选。
  3. 全序才排序。

代码 / 图示

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、流式持续输入、超内存大文件;检查堆规模、边界淘汰与外部块划分。

概念解释

  • 空与最短。
  • 极端输入。
  • 流式/超内存。

原理流程

  1. 空/单点返回。
  2. K 边界检查。
  3. 外部切块校验。

代码 / 图示

[] / [1] / 全相等
K=1 / K=n

常见误区

  • 误区:K>n 未处理;正解:按题意返回全部或报错。
  • 误区:外部排序块大小超内存;正解:按可用内存定 M。

追问

  • Q:全相等堆排? A:堆序成立,顺序不保证。
  • Q:流式无总量? A:堆常驻,无需全量。

02.5.2.4-016 堆排序与工程排序常见错误有哪些?

一句话结论

建堆方向错、下沉未选较大孩子、Top-K 堆方向反、外部排序一次性载入、多路归并未用堆、稳定性误标;按堆序、淘汰方向、I/O 流程复核。

概念解释

  • 堆序维护。
  • 淘汰方向。
  • 外部流程。

原理流程

  1. 核对堆类型。
  2. 核对堆方向。
  3. 核对归并流程。

代码 / 图示

大顶堆取大 / 小顶堆取小
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。

原理流程

  1. 标注算法与规模。
  2. 分列比较与 I/O。
  3. 标注空间。

代码 / 图示

堆排: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:堆/快选。

概念解释

  • 规模稳定空间。
  • 数据分布。
  • 局部需求。

原理流程

  1. 列约束条件。
  2. 匹配算法性质。
  3. 给出选型理由。

代码 / 图示

稳定 → 归并/计数/基数
原地 → 快排/堆排
线性 → 非比较(有前提)

常见误区

  • 误区:背单一最优算法;正解:按约束权衡。
  • 误区:忽略非比较前提;正解:值域/分布假设。

追问

  • Q:面试选型题怎么答? A:先问稳定性、空间、数据范围。
  • Q:数据特征未知? A:默认快排/归并,再按特征调整。

02.5.2.4-019 堆与排序常见追问有哪些?

一句话结论

堆排为什么不稳定、建堆为什么 O(n)、Top-K 堆方向、外部排序瓶颈、多路归并为什么用堆、工程排序混合策略、稳定性意义;回答围绕堆序维护与场景约束。

概念解释

  • 堆性质。
  • 工程场景。
  • 选型权衡。

原理流程

  1. 说堆序与下沉。
  2. 讲场景成本。
  3. 对比替代。

代码 / 图示

堆序 → 取顶淘汰 → 场景选型

常见误区

  • 误区:追问建堆复杂度答 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 个有序序列、部分排序、工程混合排序;主线是堆维护最值 + 分治归并,按数据规模与约束选型。

概念解释

  • 框架:堆/归并。
  • 变体:局部/流式/外部。
  • 工程落地。

原理流程

  1. 判断全序还是局部。
  2. 选堆/归并/非比较。
  3. 标注复杂度与空间。

代码 / 图示

最值维护:堆
有序合并:归并
超内存:外部归并

常见误区

  • 误区:变体题全排序;正解:局部需求用堆/选择。
  • 误区:外部排序套用内存算法;正解:分批 + 归并。

追问

  • Q:快速选择见哪页? A:02.5.2.2。
  • Q:归并逆序对见哪页? A:02.5.2.3。