Chapter 4 Priority Queues (Heaps)¶
§1 ADT Model¶
1. Data Objects¶
【定义】优先队列是零个或多个元素的有限有序列表。
2. Core Operations¶
优先队列的核心操作围绕优先级展开，默认删除优先级最高/最低的元素：
- PriorityQueue Initialize(int MaxElements);：初始化一个最大容量为MaxElements的优先队列
-
void Insert(ElementType X, PriorityQueue H);：向优先队列H中插入元素X -
ElementType DeleteMin(PriorityQueue H);：删除并返回优先队列H中优先级最低（值最小）的元素 -
ElementType FindMin(PriorityQueue H);：返回优先队列H中优先级最低（值最小）的元素
§2 Simple Implementations¶
分别介绍几种简单的实现方式及其时间复杂度：
1. Unordered Array¶
-
插入：在数组末尾添加元素，时间复杂度 Θ(1)
-
删除：先遍历找到最小/最大元素（Θ(n)），再删除并移动数组元素（O(n)），总时间复杂度 O(n)
2. Unordered Linked List¶
-
插入：在链表头部添加元素，时间复杂度 Θ(1)
-
删除：先遍历找到最小/最大元素（Θ(n)），再删除该节点（Θ(1)），总时间复杂度 O(n)
3. Ordered Array¶
-
插入：先找到合适的插入位置（O(n)），再移动数组元素并插入（O(n)），总时间复杂度 O(n)
-
删除：直接删除数组第一个/最后一个元素，时间复杂度 Θ(1)
优势：实际场景中删除操作次数通常不超过插入操作次数，整体性能优于无序数组/链表
4. Ordered Linked List¶
-
插入：先找到合适的插入位置（O(n)），再添加节点（Θ(1)），总时间复杂度 O(n)
-
删除：直接删除链表第一个/最后一个节点，时间复杂度 Θ(1)
5. Binary Search Tree¶
-
理论上插入和删除操作的时间复杂度均为 O(log N)
-
问题：优先队列仅需删除最小元素，会导致频繁删除左子树节点，可能使树失衡
-
改进：使用平衡二叉树（如AVL树），但会增加常数因子开销，且指针操作存在风险，同时AVL树的很多操作对优先队列来说是冗余的
五种简单实现对比:
| 实现方式 | 插入 | 删除最小值 |
|---|---|---|
| 无序数组 | Θ(1) | O(n) |
| 无序链表 | Θ(1) | O(n) |
| 有序数组 | O(n) | Θ(1) |
| 有序链表 | O(n) | Θ(1) |
| 二叉搜索树 | O(log N)* | O(log N)* |
*BST非平衡时退化为 O(N)
§3 Binary Heap¶
二叉堆是优先队列最常用的实现方式，同时满足结构性质和堆序性质。
1. Structure Property¶
【定义】完全二叉树（Complete Binary Tree）：一棵高度为h、包含n个节点的二叉树是完全二叉树，当且仅当其节点与高度为h的完美二叉树中编号从1到n的节点一一对应。
完全二叉树的性质¶
-
高度为h的完全二叉树的节点数范围：\(2ʰ ≤ n ≤ 2ʰ⁺¹ - 1\)
-
包含n个节点的完全二叉树的高度：\(h = ⌊log N⌋\)
Array Representation¶
-
完全二叉树可以用数组高效表示，通常使用
BT[n+1]（BT[0]不使用或作为哨兵） -
【引理】对于数组中索引为
i（1 ≤ i ≤ n）的节点： -
父节点索引：
⌊i/2⌋ -
左孩子索引：
2i -
右孩子索引：
2i + 1
以10个节点的完全二叉树为例，树与数组的对应关系:
[1]
/ \
[2] [3]
/ \ / \
[4] [5] [6] [7]
/ \ /
[8] [9] [10]
┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ ···│
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
根 根的 根的
左孩 右孩
父子关系:
parent[i] = ⌊i/2⌋ 例: parent[4] = 2, parent[5] = 2
left[i] = 2i 例: left[2] = 4
right[i] = 2i + 1 例: right[2] = 5
Initialize Operation¶
PriorityQueue Initialize(int MaxElements)
{
PriorityQueue H;
if (MaxElements < MinPQSize)
return Error("Priority queue size is too small");
H = malloc(sizeof(struct HeapStruct));
if (H == NULL)
return FatalError("Out of space!!!");
/* Allocate the array plus one extra for sentinel */
H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
if (H->Elements == NULL)
return FatalError("Out of space!!!");
H->Capacity = MaxElements;
H->Size = 0;
H->Elements[0] = MinData; /* set the sentinel */
return H;
}
说明：
H->Elements[0]作为哨兵，值小于堆中所有元素，用于简化插入操作的边界判断
2. Heap Order Property¶
【定义】最小树（Min Tree）：树中每个节点的键值不大于其所有子节点（若存在）的键值。 最小堆（Min Heap）：既是完全二叉树，又是最小树的二叉堆。
类比：最大堆（Max Heap） 只需将堆序性质改为"每个节点的键值不小于其所有子节点的键值"，最大元素位于根节点。
最小堆示例（元素: 3, 5, 8, 10, 12, 11, 9, 14, 15, 13）:
[1]=3
/ \
[2]=5 [3]=8
/ \ / \
[4]=10 [5]=12 [6]=11 [7]=9
/ \ /
[8]=14 [9]=15 [10]=13
验证: 每个父节点 ≤ 子节点
3≤5,8 ✓ 5≤10,12 ✓ 8≤11,9 ✓
10≤14,15 ✓ 12≤13 ✓
3. Basic Heap Operations¶
1. Insert Operation¶
-
核心思想：先将新元素插入到完全二叉树的最后一个位置（保持结构性质），再通过上滤（Percolate Up） 调整元素位置，恢复堆序性质
-
上滤过程：将新元素与其父节点比较，若新元素更小，则交换位置，直到父节点更小或到达根节点
/* H->Element[0] is a sentinel */
void Insert(ElementType X, PriorityQueue H)
{
int i;
if (IsFull(H)) {
Error("Priority queue is full");
return;
}
for (i = ++H->Size; H->Elements[i/2] > X; i /= 2)
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = X;
}
优化：使用赋值代替交换操作，减少内存访问次数 时间复杂度：O(log N)
Insert(4) 上滤过程（接续上面10元素最小堆）:
数组: [0]=-∞(哨兵) [1]=3 [2]=5 [3]=8 [4]=10 [5]=12 [6]=11 [7]=9 [8]=14 [9]=15 [10]=13
① 新元素4放入Size+1位置: [11]=4
② 4 < [11/2]=[5]=12 → 12 下移到 [11], hole 移至 [5]
③ 4 < [5/2]=[2]=5 → 5 下移到 [5], hole 移至 [2]
④ 4 > [2/2]=[1]=3 → 停止, 4 填入 [2]
上滤路径: [11] → [5] → [2] 比较次数: 3
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
最终: -∞ 3 4 8 10 5 11 9 14 15 13 12
↑新位置
2. DeleteMin Operation¶
-
核心思想：根节点即为最小值，删除根节点后，将最后一个节点移到根位置（保持结构性质），再通过下滤（Percolate Down） 调整元素位置，恢复堆序性质
-
下滤过程：将当前节点与其两个子节点中较小的一个比较，若当前节点更大，则交换位置，直到所有子节点更大或到达叶子节点
ElementType DeleteMin(PriorityQueue H)
{
int i, Child;
ElementType MinElement, LastElement;
if (IsEmpty(H)) {
Error("Priority queue is empty");
return H->Elements[0];
}
MinElement = H->Elements[1]; /* save the min element */
LastElement = H->Elements[H->Size--]; /* take last and reset size */
for (i = 1; i * 2 <= H->Size; i = Child) { /* Find smaller child */
Child = i * 2;
if (Child != H->Size && H->Elements[Child+1] < H->Elements[Child])
Child++;
if (LastElement > H->Elements[Child]) /* Percolate one level */
H->Elements[i] = H->Elements[Child];
else break; /* find the proper position */
}
H->Elements[i] = LastElement;
return MinElement;
}
思考：若省略
Child != H->Size的判断会发生什么？能否通过添加另一个哨兵来避免该判断？答: 当节点仅有左孩子而无右孩子时（出现在堆的最后一个非叶子节点），
H->Elements[Child+1]将越界访问堆外元素（可能是旧数据或未初始化的值），若该值碰巧小于左孩子，则会选错比较对象，破坏堆序。可以用哨兵避免: 在Size+1位置放置 +∞（最大堆则放 -∞），即使越界比较也不会选中。但哨兵需在每次操作后更新位置，开销比直接做Child != H->Size判断更大，故实际代码不采用。 时间复杂度：O(log N)
DeleteMin() 下滤过程（接续 Insert 后的堆，删除最小值3）:
删除前: [0]=-∞ | 3 | 4 | 8 | 10 | 5 | 11 | 9 | 14 | 15 | 13 | 12
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
① 取出 min=[1]=3, 取出末尾 last=[11]=12, Size减为10
② last=12 放到空出的 [1], 开始下滤:
[1]=□: 孩子 [2]=4, [3]=8 → min=4, 12>4 → 4上移, hole到[2]
[2]=□: 孩子 [4]=10,[5]=5 → min=5, 12>5 → 5上移, hole到[5]
[5]=□: 孩子仅[10]=13 → min=13, 12<13 → 停止, 12填入[5]
下滤路径: [1] → [2] → [5]
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
最终: -∞ 4 5 8 10 12 11 9 14 15 13
↑新根 ↑12最终位置
4. Other Heap Operations（其他堆操作）¶
注意：除最小值外，查找堆中任意其他键值需要线性扫描整个堆，时间复杂度O(N)
1. DecreaseKey(P, Δ, H)¶
-
功能：将堆H中位置P的节点的键值减少Δ（Δ>0）
-
应用：提高进程的优先级
-
实现：修改键值后，执行上滤操作
2. IncreaseKey(P, Δ, H)¶
-
功能：将堆H中位置P的节点的键值增加Δ（Δ>0）
-
应用：降低占用过多CPU时间的进程的优先级
-
实现：修改键值后，执行下滤操作
3. Delete(P, H)¶
-
功能：删除堆H中位置P的节点
-
应用：删除用户异常终止的进程
-
实现：先执行
DecreaseKey(P, ∞, H)将该节点移到根，再执行DeleteMin(H)
4. BuildHeap(H)¶
-
功能：将N个输入元素构建成一个堆
-
朴素方法：执行N次连续插入操作，时间复杂度O(N log N)
-
高效方法：从最后一个非叶子节点（索引⌊N/2⌋）开始，向前依次对每个节点执行下滤操作
-
【定理】对于包含2ʰ⁺¹ - 1个节点的完美二叉树，所有节点的高度之和为2ʰ⁺¹ - 1 - (h + 1)
-
时间复杂度：O(N)
BuildHeap 线性时间建堆过程（以 {10, 5, 3, 4, 1} 为例）:
原始数组(视为未排序完全二叉树): last_non_leaf = ⌊5/2⌋ = 2, 从 [2] 向前下滤
[1]=10 ① 下滤 [2]=5:
/ \ 孩子 [4]=4, [5]=1 → min=1
[2]=5 [3]=3 5 > 1 → swap: [2]=1, [5]=5
/ \ [5]为叶子, 停止
[4]=4 [5]=1
② 下滤 [1]=10:
[1]=10 孩子 [2]=1, [3]=3 → min=1
/ \ 10 > 1 → swap: [1]=1, [2]=10
[2]=1 [3]=3 [2]=10 继续: 孩子 [4]=4, [5]=5 → min=4
/ \ 10 > 4 → swap: [2]=4, [4]=10
[4]=4 [5]=5 [4]为叶子, 停止
[1]=1 ← 最终最小堆, 仅 O(N) 时间
/ \
[2]=4 [3]=3
/ \
[4]=10 [5]=5
§4 Applications of Priority Queues¶
Example: Find the kth Largest Element¶
问题：给定N个元素的列表和整数k，找出第k大的元素。
答: 四种常见解法及复杂度:
方法 思路 时间复杂度 ① 全排序 排序后取 A[N-k]O(N log N) ② 最大堆 BuildHeap O(N) + k次DeleteMax O(k log N) O(N + k log N) ③ 最小堆(大小k) 维护k个最大元素的堆，遍历时替换堆顶 O(N log k) ④ QuickSelect 类快排分治，仅递归含第k大的那半 O(N) 平均, O(N²) 最坏 当 k << N 时，方法③ O(N log k) 最优（接近线性）；当 k 适中时，方法② 的 O(N + k log N) 更合适；方法④ 在理论平均意义上最快。
§5 d-Heaps（d叉堆）¶
【定义】d叉堆是二叉堆的推广，其中每个节点最多有d个子节点。
Key Notes¶
- 时间复杂度：
-
DeleteMin操作需要d-1次比较来找到最小的子节点，总时间复杂度为O(d log_d N)
-
Insert操作时间复杂度仍为O(log_d N)
- 运算效率：二叉堆中2和/2操作可通过位移位快速实现，而d叉堆中的d和/d操作效率较低
- 适用场景：当优先队列过大无法完全装入主存时，d叉堆可以减少磁盘I/O次数，此时更具优势
思考：是否应该将d设置得尽可能大？
答: 不应该。 d 增大带来两方面影响:
- 有利: 树高 h = ⌈log_d N⌉ 减小，Insert 的复杂度 O(log_d N) 降低
- 不利: DeleteMin 每层需做 d-1 次比较找最小孩子，总复杂度 O(d · log_d N)
定量对比:
d Insert DeleteMin 2 (二叉) 1 · log₂ N 2 · log₂ N 4 1 · log₄ N = 0.5·log₂ N 4 · log₄ N = 2·log₂ N 8 1 · log₈ N ≈ 0.33·log₂ N 8 · log₈ N ≈ 2.67·log₂ N DeleteMin 在 d=4 时与 d=2 持平（都是 2·log₂ N），d 再大反而退化。最优 d 通常在 2~8 之间，取决于 Insert/DeleteMin 操作的比例。此外，二叉堆的 ×2/÷2 可用位运算加速，d叉堆则需实际乘除，常数因子更大。
d叉堆 vs 二叉堆示意:
二叉堆 (d=2): d叉堆 (d=4):
[1] ┌──[1]──┐
/ \ ┌─┐ ┌┼┐ ┌─┐
[2] [3] [2][3][4][5]
/ \ / \ /|\ ...
[4] [5] [6] [7]
树高 ≈ log₂N 树高 ≈ log₄N (更矮)
DeleteMin: 1次比较/层 DeleteMin: 3次比较/层