面试题库 › 客户端 › 建堆(自顶向下/自底向上)的时间复杂度

建堆(自顶向下/自底向上)的时间复杂度

难度 ★★☆在 2 场真实面经中被问到 方向:客户端考点:排序算法

哪些公司问过

字节跳动1毫末智行1

常见岗位:游戏客户端、C/C++ 软件开发

答案要点

  1. 自顶向下:逐个插入并上浮,总复杂度 O(n log n)
  2. 自底向上:从下标 n/2-1 开始向前逐个下沉,总复杂度 O(n)
  3. O(n) 的原因:下沉代价与高度成正比,高度大的节点数量少,级数求和收敛
  4. 自顶向下慢在上浮代价与深度成正比,而深层节点最多
  5. 批量建堆用自底向上,数据流式到达时只能逐个插入;堆排序整体仍是 O(n log n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题