20. Heaps and PQs

Priority Queue

PQ 是一种抽象数据类型，它维护一个集合，并能始终高效地访问和操作当前最小（或最大）元素。

当我们有 N 个数据，但只关心其中最大的 M 个时：

• 传统方法是排序所有数据（慢且占用 Θ(N) 空间）
• PQ 的做法是只维护一个大小为 M 的集合
• 每加入一个新元素，如果超过 M，就删除当前最小的元素（最不重要的）

这样可以将空间优化到 Θ(M)，并且用堆实现时操作效率为 $O(log M)$

Heaps 堆

二叉最小堆需要满足的条件：

1. Complete：只有最底层可以有缺失的项目，并且其余所有节点都要尽可能靠左排列
2. Min-heap：每个节点的值均小于或等于其两个子节点的值（根的值最小，它的子节点都比它大）

Add 方法：

• 将需要添加的值暂时添加到最底端（满足二叉最小堆的下一个位置）
• 逐步向上调换，直到找到它的位置

删除最小值方法：

• 删除根节点的值
• 将最底端的值移动到根节点，将它逐步向下调换，直到找到它的位置

Tree Representations of Heaps

将 key 存放在一个数组中，而不需要其他任何结构，例如不需要创建一个 parent 表 （Disjoint Sets 中的方法）

计算方式：

• 这里假设数组从 1 开始编号
• 左子节点(k) = k * 2
• 右子节点(k) = k * 2 + 1
• 父节点(k) = k / 2

运行时间分析：

数据结构总结

详见幻灯片