文章目录
- 💎 定义：什么是大根堆 / 小根堆
- 如何用一维数组存储堆
- 💎 基本操作： 下滤 上滤
- 下滤：把根节点向下调整的操作，复杂度 O(log N)
- 上滤：把最后一个元素向上调整的操作，复杂度 O(log N)
- 💎 建堆：自上向下 & 自下向上
- 自上向下 复杂度为 O(N log N)，对应上滤操作
- 自下向上 复杂度为 O(N)，对应下滤操作
- 💎 应用：优先队列 & 堆排序
- 优先队列：小根堆
- 堆排序：将优先队列的所有元素依次弹出即可
💎 定义：什么是大根堆 / 小根堆
- 大根堆: 一棵完全二叉树 & 堆序性为：每个节点 ≥ 它的子节点
- 🐾 后续说明以大根堆为例，小根堆同理但反之操作即可
- 小根堆: 一棵完全二叉树 & 堆序性为：每个节点 ≤ 它的子节点
如何用一维数组存储堆
- 堆可以用一个一维数组存储，对于节点
i
- 左子节点下标为
2i +1- 右子节点下标为
2i +2
💎 基本操作： 下滤 上滤
下滤：把根节点向下调整的操作，复杂度 O(log N)
- 如果
破坏堆序性的元素小于他的最大子节点，则与之交换；持续比较&交换，直到该元素大于他的子节点为止
- 此时，重新被调整成为了一个大根堆
上滤：把最后一个元素向上调整的操作，复杂度 O(log N)
- 主要用于插入新元素到堆中
- 如果
破坏堆序性的元素大于他的父节点，则与之交换；持续比较&交换，直到该元素小于他的父节点为止
- 此时，重新被调整成为了一个大根堆
💎 建堆：自上向下 & 自下向上
自上向下 复杂度为 O(N log N)，对应上滤操作
- 将元素利用上滤，一个一个插入到堆内
自下向上 复杂度为 O(N)，对应下滤操作
- 自下向上，下滤每个父节点
💎 应用：优先队列 & 堆排序
优先队列：小根堆
- 小根堆根节点本来就是最小元素，直接弹出根节点可完成
弹出最小元素操作；弹出后要将剩余的元素调整为堆 (将最后一个元素放到根节点，然后下滤)：弹出复杂度O(N log N) - 插入操作直接应用上滤即可完成：插入复杂度
O(N log N)
堆排序：将优先队列的所有元素依次弹出即可
- 考虑到空间复杂度：进一步，排序的结果可以存放到空缺的堆单元里
- 用
大根堆，每次弹出的元素存储到最后，这样排序完的序列是正序的- 以第一步为例：弹出 10，放入 最后一个元素的位置 (初始时 2 所在)；然后刚好本来 2 就要移入根节点的位置，刚好空缺出
...... 
B站视频参考：【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆】
