面试题库 › C++ / 后端 › 堆排序的实现

堆排序的实现

难度 ★★☆在 21 场真实面经中被问到 方向:C++ / 后端考点:排序算法

哪些公司问过

字节跳动5百度3快手2腾讯音乐2腾讯1拼多多1vivo1奇安信1蚂蚁集团1BOSS直聘1多益网络苏州1阿里巴巴、腾讯、滴滴、字节跳动1

常见岗位:NLP / 语音、C++ 后端、Java 后端、Go 后端、人工智能

答案要点

  1. 第一步建大顶堆:从最后一个非叶子节点 n/2-1 开始向前依次下沉,时间 O(n)
  2. 下沉:与较大的孩子交换,直到满足堆性质
  3. 第二步:反复交换堆顶与末尾元素,堆大小减一,再对堆顶下沉
  4. 时间 O(n log n),原地、空间 O(1),不稳定
  5. 最坏仍为 O(n log n),适合 TopK;缓存表现不如快排

易错点

面试官常见追问

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

相关面试题