堆排序的实现
哪些公司问过
答案要点
- 第一步建大顶堆:从最后一个非叶子节点 n/2-1 开始向前依次下沉,时间 O(n)
- 下沉:与较大的孩子交换,直到满足堆性质
- 第二步:反复交换堆顶与末尾元素,堆大小减一,再对堆顶下沉
- 时间 O(n log n),原地、空间 O(1),不稳定
- 最坏仍为 O(n log n),适合 TopK;缓存表现不如快排
易错点
- 建堆从下标 0 开始,而不是 n/2-1
- 下沉时没有选较大的孩子
- 排序阶段忘了缩小堆的范围
- 把堆排序说成稳定排序
面试官常见追问
- 为什么建堆是 O(n) 而不是 O(n log n)?
- 堆排序为什么不稳定?
- 升序为什么用大顶堆?
- 堆排序和快排怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场