主题
面试速答（先看这里）
**一句话结论：**小顶堆是一种二叉堆数据结构，它可以使用数组来实现。
60秒标准回答：
小顶堆（Min Heap）是一种特殊的二叉堆数据结构，它满足以下性质：对于堆中的任意节点i，其父节点的值小于等于节点i的值。换句话说，堆中的最小值总是位于堆的根节点上
小顶堆是一种二叉堆数据结构，它可以使用数组来实现
小顶堆常用于解决与最小值相关的问题，所以在实际应用中非常的广泛，比如
**答题顺序：**结论 → 原理/机制 → 关键流程 → 场景与取舍 → 易错点
回答主线：
- **要点1：**小顶堆（Min Heap）是一种特殊的二叉堆数据结构，它满足以下性质：对于堆中的任意节点i，其父节点的值小于等于节点i的值。
- **要点2：**2、排序，小顶堆可以用于堆排序，可以把一个数组构建成小顶堆，那么就是实现了从小到大的排序。
- **要点3：**3、 定时器 ，在定时器的实现中，可以使用小顶堆来管理即将触发的定时事件。
- **要点4：**4、Dijkstra算法：在最短路径问题中，Dijkstra算法使用优先级队列来选择当前最短路径的下一个节点，而小顶堆可以用作实现该优先级队列。
- **要点5：**5、 优先级队列 ：小顶堆可以用作优先级队列的底层数据结构，在O(log n)时间内进行插入和删除操作，O(1)时间内获取最小优先级元素。
**记忆锚点：**Dijkstra → Heapify → 优先级队列 → PriorityQueue → 特殊的二叉堆数据结构 → 触发时间戳的数据结构
加分表达：
- 如果新元素的值比父节点的值小，则交换它们，并继续向上比较和交换，直到满足小顶堆的性质（即新元素的值不小于其父节点的值），或者到达堆的根节点。
- 如果新根节点的值比其子节点的值大，则交换它们，并继续向下比较和交换，直到满足小顶堆的性质（即新根节点的值不大于其子节点的值），或者到达叶子节点。
追问准备：
- 围绕「Dijkstra」：底层原理是什么？使用时有哪些边界和常见坑？
- 围绕「Heapify」：底层原理是什么？使用时有哪些边界和常见坑？
- 围绕「优先级队列」：底层原理是什么？使用时有哪些边界和常见坑？
- 如果线上出现异常，你会如何定位、验证并规避？
典型回答
小顶堆（Min Heap）是一种特殊的二叉堆数据结构，它满足以下性质：对于堆中的任意节点i，其父节点的值小于等于节点i的值。换句话说，堆中的最小值总是位于堆的根节点上。
小顶堆是一种二叉堆数据结构，它可以使用数组来实现。
小顶堆常用于解决与最小值相关的问题，所以在实际应用中非常的广泛，比如：
1、查找最小值，在一群数字中，查找最小值，可以利用小顶堆，小顶堆的根节点就是最小值。
如：从10亿个数字中，取出最小的10个数
2、排序，小顶堆可以用于堆排序，可以把一个数组构建成小顶堆，那么就是实现了从小到大的排序。
3、定时器，在定时器的实现中，可以使用小顶堆来管理即将触发的定时事件。每个定时事件可以表示为一个包含触发时间戳的数据结构。从堆顶不断取出需要执行的定时任务即可。
4、Dijkstra算法：在最短路径问题中，Dijkstra算法使用优先级队列来选择当前最短路径的下一个节点，而小顶堆可以用作实现该优先级队列。
5、优先级队列：小顶堆可以用作优先级队列的底层数据结构，在O(log n)时间内进行插入和删除操作，O(1)时间内获取最小优先级元素。如Java 中的 PriorityQueue
6、查找最大值，有的时候，为了节省空间，也么用小顶堆实现海量数据的最大值查找。
扩展知识
插入过程
小顶堆的插入主要有两个步骤：
- 1、将新元素添加到小顶堆的最后一个位置（数组的末尾）。
- 2、执行"上浮"（Heapify Up）操作：将新插入的元素与其父节点进行比较。如果新元素的值比父节点的值小，则交换它们，并继续向上比较和交换，直到满足小顶堆的性质（即新元素的值不小于其父节点的值），或者到达堆的根节点。
加入有一个以下小顶堆，当我们插入一个元素3的时候。
将3添加到堆的最后位置：
执行上浮操作，将3上浮到正确位置：
删除过程
小顶堆的删除主要有两个步骤：
- 1：将堆顶元素（最小值）删除，并用堆的最后一个元素（数组的最后一个元素）来替换它。
- 2：执行"下沉"（Heapify Down）操作：将新的根节点与其较小的子节点进行比较。如果新根节点的值比其子节点的值大，则交换它们，并继续向下比较和交换，直到满足小顶堆的性质（即新根节点的值不大于其子节点的值），或者到达叶子节点。
以下是删除3这个元素的过程：
经过几轮下沉后：
