建堆(自顶向下/自底向上)的时间复杂度
哪些公司问过
字节跳动1毫末智行1
答案要点
- 自顶向下:逐个插入并上浮,总复杂度 O(n log n)
- 自底向上:从下标 n/2-1 开始向前逐个下沉,总复杂度 O(n)
- O(n) 的原因:下沉代价与高度成正比,高度大的节点数量少,级数求和收敛
- 自顶向下慢在上浮代价与深度成正比,而深层节点最多
- 批量建堆用自底向上,数据流式到达时只能逐个插入;堆排序整体仍是 O(n log n)
易错点
- 认为两种建堆方式复杂度都是 O(n log n)
- 自底向上时从前往后遍历,导致子树还没调整好就下沉父节点
- 把建堆的 O(n) 当作堆排序的整体复杂度
面试官常见追问
- 具体如何建堆?
- 堆排序的复杂度和稳定性?
- 为什么从 n/2-1 开始?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场