面试题库 › 嵌入式 › 大根堆与小根堆的区别及动态维护 TopK

大根堆与小根堆的区别及动态维护 TopK

难度 ★★☆在 2 场真实面经中被问到 方向:嵌入式考点:栈与队列

哪些公司问过

深信服1锐捷1

常见岗位:嵌入式软件、C/C++ 软件开发

答案要点

  1. 都是用数组存储的完全二叉树,大根堆堆顶最大,小根堆堆顶最小
  2. 取堆顶 O(1),插入上浮和删除堆顶下沉均为 O(log n)
  3. 自底向上建堆的时间复杂度是 O(n)
  4. 动态求最大的 K 个用大小为 K 的小根堆,堆顶即第 K 大
  5. 场景:优先队列、堆排序、定时器、多路归并、中位数维护

易错点

面试官常见追问

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

相关面试题