堆与优先队列

1. 一句话总结

堆是满足父子大小关系的完全二叉树，优先队列可用堆快速取最大或最小元素。

2. 通俗解释

堆像按优先级排队，不保证所有人完全有序，但保证队首一定是当前优先级最高或最低的人。

3. 核心概念

• 大根堆：父节点大于等于子节点，堆顶最大。
• 小根堆：父节点小于等于子节点，堆顶最小。
• 完全二叉树：最后一层从左到右填。
• 优先队列：每次取优先级最高的元素。
• 堆排序：建堆后反复取堆顶。

4. 底层原理

• 堆通常用数组存储，父子下标可计算。
• 插入先放末尾再上浮，O(log n)。
• 删除堆顶用末尾替换再下沉，O(log n)。
• 建堆可 O(n) 完成，不是 O(nlogn)。
• Top K 常用固定大小堆降低空间。

5. 面试标准回答

堆是一种基于完全二叉树的结构，只要求父子节点满足大小关系，不要求整体完全有序。大根堆堆顶最大，小根堆堆顶最小。堆常用数组实现，插入时元素上浮，删除堆顶时元素下沉，复杂度都是 O(log n)。优先队列常用堆实现，适合动态获取最大或最小元素，例如 Top K、任务调度、定时器和 Dijkstra。堆排序 O(nlogn)，原地但不稳定。

6. 高频追问

追问 1：堆与优先队列面试第一句话怎么答？

先给结论：大根堆：父节点大于等于子节点，堆顶最大。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

堆通常用数组存储，父子下标可计算。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：插入先放末尾再上浮，O(log n)。

追问 5：实际开发中怎么体现？

任务调度按优先级取任务。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• 任务调度按优先级取任务。
• 海量数据 Top K 用固定大小堆。
• 定时器常用小根堆按过期时间排序。

9. 背诵速记

堆是完全二叉树，堆顶保证最大或最小。插入上浮 O(log n)，删除堆顶下沉 O(log n)，建堆 O(n)。优先队列、Top K、定时器都常用堆。