定义
最小堆是一种满足特定顺序规则的堆结构：
任意一个节点的值，都小于等于它的子节点的值也就是：
parent <= leftChild
parent <= rightChild所以最小堆最核心的性质是：
堆顶元素一定是整个堆中的最小值例如：
1
/ \
3 2
/ \ / \
7 6 5 4这是一个最小堆，因为每个父节点都小于等于自己的子节点。
注意：最小堆不是全局有序
最小堆只保证 父子之间有序，不保证同一层之间有序，也不保证左右子树整体有序。
例如：
1
/ \
5 2
/ \ / \
9 8 6 3这也是最小堆。
因为它满足：
1 <= 5
1 <= 2
5 <= 9
5 <= 8
2 <= 6
2 <= 3但是你会发现：
左子树的 5 比右子树的 2 大
同一层也不是从小到大排列所以最小堆不能理解成“排序好的树”。
它只保证：
每个局部的父节点 <= 子节点堆顶
最小堆的堆顶就是根节点。
因为所有节点都满足父节点小于等于子节点，所以最上面的根节点一定是最小值。
如果用数组表示，堆顶就是：
heap[0]所以获取最小值非常快：
peek 操作：O(1)上浮 sift up
当插入一个新元素时，通常先放到堆的末尾。
但是这个新元素可能比它的父节点小，破坏最小堆规则，所以需要不断向上交换。
这个过程叫 上浮。
例如当前堆是：
[1, 3, 2, 7, 6, 5]插入 0：
[1, 3, 2, 7, 6, 5, 0]此时 0 比父节点小，所以向上交换：
[1, 3, 0, 7, 6, 5, 2]继续比较，0 还是比父节点 1 小：
[0, 3, 1, 7, 6, 5, 2]完成。
上浮的本质：
新节点不断和父节点比较
如果比父节点小，就交换
直到父节点更小，或者到达堆顶时间复杂度：
O(log n)下沉 sift down
当删除堆顶时，会破坏最小堆结构。
通常做法是：
1. 取出堆顶最小值
2. 用最后一个节点替换堆顶
3. 从堆顶开始向下调整向下调整的过程叫 下沉。
例如：
[1, 3, 2, 7, 6, 5]删除堆顶 1，用最后一个元素 5 放到堆顶：
[5, 3, 2, 7, 6]现在 5 比子节点 2 大，违反最小堆规则。应该和两个子节点中更小的那个交换：
[2, 3, 5, 7, 6]完成。
下沉的本质：
当前节点和左右子节点比较
如果当前节点比更小的子节点大，就交换
一直交换到满足最小堆规则时间复杂度：
O(log n)常见操作
| 操作 | 含义 | 时间复杂度 |
|---|---|---|
peek | 查看最小值 | O(1) |
push | 插入元素 | O(log n) |
pop | 删除并返回最小值 | O(log n) |
heapify | 把普通数组建成堆 | O(n) |
heapify 是什么
heapify 指的是把一个普通数组调整成堆。
例如普通数组：
[5, 3, 8, 1, 2]经过 heapify 后，可能变成：
[1, 2, 8, 3, 5]只要满足最小堆性质即可，不要求结果唯一。
heapify 常见做法是从最后一个非叶子节点开始，依次向前做下沉操作。
时间复杂度是：
O(n)注意不是 O(n log n)，这是堆的一个常见考点。
最小堆和优先队列的关系
最小堆是实现优先队列的一种常见方式。
优先队列的特点是：
不是按插入顺序取元素，而是按优先级取元素如果优先级越小越先处理，就可以用最小堆。
例如任务队列：
任务 A：优先级 5
任务 B：优先级 1
任务 C：优先级 3用最小堆时，最先取出的是：
任务 B：优先级 1最小堆常见场景
最小堆适合解决这类问题：
需要频繁拿到当前最小值
但又不想每次都重新排序典型场景：
| 场景 | 用法 |
|---|---|
| 第 K 大元素 | 维护大小为 K 的最小堆 |
| 合并 K 个有序链表 | 每次取当前最小头节点 |
| 数据流中位数 | 和最大堆配合使用 |
| Dijkstra 最短路径 | 每次取当前距离最小的点 |
| 定时任务调度 | 每次取最近要执行的任务 |
和排序数组的区别
如果你用排序数组维护最小值：
取最小值：O(1)
插入新元素：O(n)
删除最小值：O(1) 或 O(n)如果用最小堆：
取最小值：O(1)
插入新元素：O(log n)
删除最小值：O(log n)所以当问题需要频繁插入、删除、取最小值时，最小堆比排序数组更合适。
一句话理解
最小堆是一种“局部有序”的结构，它不保证整体排序，但保证堆顶永远是最小值；通过上浮和下沉，可以在 O(log n) 时间内完成插入和删除最小值。