定义
- 优先队列: 具有出队优先级的队列, 通常用堆来实现
- 许多编程语言提供的是优先队列（priority queue），这是一种抽象的数据结构，定义为具有优先级排序的队列。堆通常用于实现优先队列，大根堆相当于元素按从大到小的顺序出队的优先队列. 因此, 从使用角度上, 可以将优先队列和堆看做等价的数据结构.
- 堆（heap）是一种满足特定条件的完全二叉树，主要可分为小根堆和大根堆
- 小根堆: 任意节点的值≤其子节点的值, 大根堆反之
特性
- 最底层节点靠左填充，其他层的节点都被填满 → 完全二叉树。
- 完全二叉树没有空白节点, 适合用数组顺序存储堆适合用数组存储, 元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。
- 若从 开始标号, 对节点 , 表示左儿子, 表示右儿子, 表示父节点
- 若从0开始标号, 则对索引i，其左子节点的索引为 ，右子节点的索引为 ，父节点的索引为 （向下整除）。
- 当索引越界时，表示空节点或节点不存在。
- 可以将索引映射公式封装成函数，方便后续使用
- 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。
- 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。
常用操作
插入
(从堆底)入堆 → 添加元素到堆底, 可能破坏堆的结构, 故需要从入堆节点开始从底至顶堆化(heapify up), 一直到越过根节点或遇到无需交换的节点处结束. 时间复杂度
出堆
(堆顶元素)出堆 → 交换堆顶元素与堆底元素, 然后将堆底从列表中删除, 最终从顶至底执行堆化(heapify down), 直到越过叶节点或遇到无须交换的节点时结束. 时间复杂度
建堆
- 借助入堆操作实现 → 对列表内每个元素执行入堆, 元素从下往上跑, 堆自上而下构建. 时间复杂度
- 通过遍历堆化实现
- 将列表所有元素原封不动地添加到堆中，此时堆的性质尚未得到满足。
- 倒序遍历堆（层序遍历的倒序），依次对每个非叶节点执行“从顶至底堆化(
down)”, 即将其作为根节点堆化其子树。
叶节点由于没有子堆, 所以天然是合法子堆, 不需要堆化
由于完全二叉树底层节点数远大于其他节点数, 故时间复杂度优化到
堆排序
- 建堆 → 不停出堆
- 时间复杂度为
- 是一种非稳定排序：在交换堆顶元素和堆底元素时，相等元素的相对位置可能发生变化, 不能维持在原序列中的顺序
- 题目中带*的元素就是为了区分该顺序而存在的
Top-k问题
- 找到一个序列中最大的k个数, 可以基于堆高效地解决
- 初始化一个小顶堆，其堆顶元素最小。
- 先将数组的前k个元素依次入堆。
- 从第 k+1 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
- 遍历完成后，堆中保存的就是最大的 k 个元素。
总共执行了 轮入堆和出堆，堆的最大长度为 ，因此时间复杂度为 。该方法的效率很高，当 k 较小时，时间复杂度趋向 ；当 k 较大时，时间复杂度不会超过 。
只有大于当前 个的数才有顶替的资格
- 另外，该方法适用于动态数据流的使用场景。在不断加入数据时，我们可以持续维护堆内的元素，从而实现最大的k个元素的动态更新。
问答
Q：数据结构的“堆”与内存管理的“堆”是同一个概念吗？
A: 两者不是同一个概念，只是碰巧都叫“堆”。计算机系统内存中的堆是动态内存分配的一部分，程序在运行时可以使用它来存储数据。程序可以请求一定量的堆内存，用于存储如对象和数组等复杂结构。当这些数据不再需要时，程序需要释放这些内存，以防止内存泄漏。相较于栈内存，堆内存的管理和使用需要更谨慎，使用不当可能会导致内存泄漏和野指针等问题。
