返回：0300 数据结构总目录 · 上一章：0309 Chap9 词典 · 下一章：0311 Chap11 串

1、学习目标

优先级队列不是按进入时间出队，而是按优先级出队。普通队列关心“先来先服务”，优先级队列关心“当前最重要的是谁”。

模块 要掌握的内容
ADT insert、getMax、delMax
完全二叉堆 数组表示、父子下标关系
上滤 插入后向上恢复堆序
下滤 删除堆顶后向下恢复堆序
批量建堆 Floyd 自底向上建堆
堆排序 原地排序、复杂度、稳定性
拓展 左式堆、d 叉堆

2、资料范围

PDF 课件 内容
10.Pq.A.Basic_Implementation.pdf 优先级队列基本实现
10.Pq.B.Complete_Binary_Heap.pdf 完全二叉堆
10.Pq.C.Tournamentsort.pdf 锦标赛排序
10.Pq.D.Heapsort.pdf 堆排序
10.Pq.XA.Leftist_Heap.pdf 左式堆
10.Pq.XB.d-heap.pdf d 叉堆

3、优先级队列 ADT

以最大优先级队列为例：

操作 含义
insert(e) 插入元素
getMax() 查看最大元素
delMax() 删除并返回最大元素

可以用无序向量、有序向量、列表、堆实现：

实现 插入 取最大 删除最大
无序向量 O(1) O(n) O(n)
有序向量 O(n) O(1) O(1)
完全二叉堆 O(log n) O(1) O(log n)

堆是折中方案：插入和删除都足够快，取堆顶非常快。

4、完全二叉堆

完全二叉堆同时满足两个性质：

  1. 结构性：形状是完全二叉树。
  2. 堆序性：父节点优先级不低于孩子。

数组下标关系，假设从 0 开始：

位置 下标
父节点 (i - 1) / 2
左孩子 2 * i + 1
右孩子 2 * i + 2

堆不是 BST。堆只保证父子局部有序，不保证左子树都小于右子树，也不支持中序有序遍历。

5、插入与上滤

插入新元素时，先放到数组末尾，保持完全二叉树形状；再不断和父节点比较，若优先级更高就交换。

1
2
3
4
5
6
7
8
void percolateUp(int i) {
    while (i > 0) {
        int p = (i - 1) / 2;
        if (heap[p] >= heap[i]) break;
        swap(heap[p], heap[i]);
        i = p;
    }
}

上滤最多走树高层，所以复杂度 O(log n)。

6、删除与下滤

删除最大元素时：

  1. 保存堆顶。
  2. 用末尾元素覆盖堆顶。
  3. 删除末尾。
  4. 从根开始下滤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void percolateDown(int i, int n) {
    while (true) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int best = i;

        if (l < n && heap[l] > heap[best]) best = l;
        if (r < n && heap[r] > heap[best]) best = r;
        if (best == i) break;

        swap(heap[i], heap[best]);
        i = best;
    }
}

下滤每层选择更大的孩子交换，保证局部最大值向上移动。

7、批量建堆

如果逐个插入 n 个元素，复杂度是 O(n log n)。Floyd 建堆从最后一个内部节点开始，自底向上做下滤：

1
2
3
for (int i = n / 2 - 1; i >= 0; --i) {
    percolateDown(i, n);
}

虽然单次下滤最坏 O(log n)，但低层节点很多、可下滤高度很小，总复杂度为 O(n)。

复盘时要能说清楚：Floyd 建堆不是每个节点都走 log n 层，所以不能粗暴估成 O(n log n)。

8、堆排序

堆排序过程：

  1. 对原数组建最大堆。
  2. 交换堆顶和末尾。
  3. 缩小堆规模。
  4. 对堆顶下滤。
  5. 重复直到堆为空。
1
2
3
4
5
heapify(a);
for (int n = a.size(); n > 1; --n) {
    swap(a[0], a[n - 1]);
    percolateDown(0, n - 1);
}

特点：

项目 说明
时间复杂度 O(n log n)
空间复杂度 原地 O(1)
稳定性 不稳定
优点 最坏情况有保障
缺点 缓存局部性和常数通常不如快排

9、左式堆

左式堆适合高效合并两个优先级队列。

核心概念是空节点路径长度 npl：

1
npl(x) = x 到最近外部节点的距离

左式堆性质：

1
npl(left) >= npl(right)

这使得右侧路径较短，合并时沿右链递归，复杂度为 O(log n)。

合并思路：

  1. 选择堆顶更大的堆作为根。
  2. 递归合并它的右子堆和另一个堆。
  3. 若左子树 npl 小于右子树，则交换左右孩子。
  4. 更新 npl。

10、d 叉堆

d 叉堆把每个节点的孩子数从 2 扩展到 d。

操作 影响
树高 约为 log_d n，比二叉堆低
上滤 父节点更少，可能更快
下滤 每层要从 d 个孩子中选最优
场景 Dijkstra 等大量 decrease-key 或插入的场合

d 越大不一定越好，因为下滤每层比较次数会增加。工程上要看操作比例。

11、复杂度汇总

操作 完全二叉堆 左式堆
getMax O(1) O(1)
insert O(log n) O(log n)
delMax O(log n) O(log n)
heapify O(n) -
merge 不擅长 O(log n)
堆排序 O(n log n) -

12、易错点

易错点 修正
把堆当成 BST 堆只保证父子优先级，不保证中序有序
建堆写成逐个插入 Floyd 建堆能做到 O(n)
下滤只比较左孩子 要选左右孩子中更优的那个
认为堆排序稳定 堆排序通常不稳定
左式堆只看左右子树大小 左式堆看的是 npl，不是节点数

13、复盘清单

检查项 状态
能写出堆数组的父子下标公式 待复盘
能手写上滤和下滤 待复盘
能解释 Floyd 建堆为什么是 O(n) 待复盘
能手动模拟堆排序前两轮 待复盘
能说明堆和 BST 的区别 待复盘
能解释左式堆适合合并的原因 待复盘