大根堆、小根堆与优先队列
答案要点
- 大根堆每个节点 ≥ 子节点,小根堆每个节点 ≤ 子节点,都是完全二叉树
- 数组存储:节点 i 的孩子为 2i+1、2i+2,父节点为 (i−1)/2
- 插入上浮、删除堆顶下沉均为 O(log n),取堆顶 O(1)
- 自底向上建堆 O(n),堆排序 O(n log n) 且不稳定
- 优先队列通常基于堆实现;C++ 默认大根堆,Java 默认小根堆
易错点
- 把堆当成二叉搜索树,以为堆整体有序
- 记错 C++ 和 Java 优先队列的默认顺序
- 认为建堆复杂度是 O(n log n)
面试官常见追问
- 为什么建堆是 O(n) 而不是 O(n log n)?
- 求最大的 K 个数用大根堆还是小根堆?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。