堆排序适用于哪些场景
哪些公司问过
途游1
答案要点
- 时间复杂度稳定 O(n log n),原地排序,空间 O(1),但不稳定
- 缓存局部性差,实际速度通常不如快排,可作为内省排序的兜底
- Top K:维护大小为 K 的堆,O(n log K),适合海量或流式数据
- 优先队列:任务调度、定时器、Dijkstra、合并 K 个有序链表
- 双堆维护数据流中位数;自底向上建堆为 O(n)
易错点
- 误以为堆排序是稳定排序
- 求最大 K 个数用了大顶堆,导致需要把全部数据入堆
- 以为建堆复杂度是 O(n log n)
面试官常见追问
- 为什么自底向上建堆是 O(n)?
- 求最大的 K 个数为什么用小顶堆?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场