堆(优先队列的底层结构)
哪些公司问过
答案要点
- 堆:满足堆性质的完全二叉树;大顶堆父不小于子,小顶堆父不大于子
- 数组存储(下标从 0):左孩子 2i+1,右孩子 2i+2,父节点 (i-1)/2
- 插入:放在末尾后上浮,O(log n);删除堆顶:末尾元素换到堆顶后下沉,O(log n)
- 建堆:从最后一个非叶子节点开始下沉,O(n)
- 应用:优先队列、堆排序、TopK、Dijkstra;与内存中的堆区概念不同
易错点
- 把数据结构的堆和内存里的堆混为一谈
- 说在堆里可以用二分查找
- 下标计算错误(从 0 还是从 1 开始)
- 建堆时从根开始,而不是从最后一个非叶子节点
面试官常见追问
- 在最小堆中查找某个元素的复杂度是多少?
- 堆和二叉搜索树有什么区别?
- 堆和栈的区别与内存空间布局?
- 为什么建堆是 O(n) 而不是 O(n log n)?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。