第 6 章优先队列

Priority Queue and Heap

引入

假设我们正在写一个网络模拟器。系统中不断产生未来事件：

10.2 ms：数据包到达路由器
7.8 ms：定时器超时
12.5 ms：下一次重传
8.1 ms：链路恢复

这些事件不是按“加入容器的顺序”执行，而必须始终取出时间戳（timestamp）最小的事件。处理一个事件后，还可能立即插入新的未来事件。

如果每次都扫描整个线性表寻找最早事件，事件数一大，重复查找的成本会非常高。

怎样既允许事件不断加入，又能快速取出当前最早、最大或最小的那个对象？

“下一步该处理谁”是一个非常普遍的问题

同一种需求还出现在：

操作系统调度：从就绪任务中选择下一项
Dijkstra：反复取出当前暂定距离最小的顶点
Huffman 编码：反复取出频率最小的两个节点合并
智能体调度器：定时工具调用、重试、超时等事件可按下一次运行时间放进最小堆（min-heap）

这些场景并不要求“整体排好序”，它们真正反复执行的是两件事：插入一个新对象，以及取出当前极值。

优先队列就是对这类工作负载的抽象；而堆的价值在于，它不追求所有元素完全有序，只维护足以支持高效极值访问的局部结构。

学习目标

掌握优先队列抽象数据类型（Abstract Data Type，ADT）
比较无序线性表、有序线性表和堆实现
掌握最大堆（max-heap）、最小堆和完全二叉树（complete binary tree）数组表示
掌握插入的上滤（percolate up）和删除堆顶的下滤（percolate down）
掌握 Floyd 建堆和复杂度分析
理解堆排序（heap sort）的稳定性（stability），以及它为什么不稳定
使用堆解决第 K 大元素问题

本章路线图

优先队列
Priority Queue

抽象数据类型与实现选择
谁先出队由优先级决定二叉堆（binary heap）
完全二叉树 + 堆序性质（heap-order property）数组表示
完全二叉树映射到数组核心操作
插入上滤 · 删除下滤线性建堆
Floyd 为什么是 O(n) 堆排序
原地排序 · 不稳定典型应用
第 K 大元素 · 事件模拟

优先队列

优先队列抽象数据类型

最大优先队列：

操作	含义
`create()`	创建空优先队列
`size()`	返回元素个数
`max()`	返回最大优先级元素
`insert(x)`	插入元素
`deleteMax()`	删除并返回最大优先级元素

最小优先队列把 max/deleteMax 换成 min/deleteMin。

线性表实现

表示	插入	查找最大	删除最大
无序线性表	\(\Theta(1)\)	\(\Theta(n)\)	\(\Theta(n)\)
有序线性表	\(\Theta(n)\)	\(\Theta(1)\)	\(\Theta(1)\) 或 \(\Theta(n)\)
二叉堆	\(O(\log n)\)	\(O(1)\)	\(O(\log n)\)

堆在插入和删除之间取得平衡。

二叉堆

堆定义

最大堆满足：

是完全二叉树
每个结点的值不小于它的孩子

最小堆满足：

是完全二叉树
每个结点的值不大于它的孩子

堆不要求左右子树之间有全局有序关系。

最大堆示例

根结点一定是最大值。

0-based 数组表示

本章所有堆操作都使用 0-based 下标：根结点位于 heap[0]。

堆操作

最大堆类骨架

static final class MaxHeap<T extends Comparable<? super T>> {
  private final ArrayList<T> heap;
  private final int capacity;

  MaxHeap(int capacity) {
    if (capacity <= 0) {
      throw new IllegalArgumentException("capacity must be positive");
    }
    this.capacity = capacity;
    heap = new ArrayList<>(capacity);
  }

  boolean isEmpty() {
    return heap.isEmpty();
  }

  int size() {
    return heap.size();
  }

  T max() {
    if (isEmpty()) {
      throw new NoSuchElementException("heap is empty");
    }
    return heap.get(0);
  }

MaxHeap 同时维护两条不变量：数组表示完全二叉树，父结点不小于孩子。

heap 保存 0-based 连续数组，capacity 只限制可容纳的元素数。

构造函数建立空堆；此时数组长度就是逻辑元素数，没有额外占位槽。

合法容量确定后直接分配 0-based 存储，后续有效下标始终是 0..size-1。

isEmpty() 判断是否存在根结点。

数组为空就等价于堆为空，因此该判断是 O(1)。

size() 返回当前完全二叉树的结点数。

有效元素构成连续前缀，所以数组长度可以直接作为堆大小。

max() 读取最大优先级元素，但不改变堆结构。

空堆没有合法根结点，因此读取最大值前必须检查边界。

空堆查询没有定义结果，用异常明确拒绝该操作。

最大堆的全局最大值必在根；0-based 表示中根就是 heap[0]，所以查询为 O(1)。

插入：上滤过程

插入：上滤代码

void insert(T value) {
  Objects.requireNonNull(value, "value");
  if (size() == capacity) {
    throw new IllegalStateException("heap capacity exceeded");
  }
  heap.add(value);
  int child = size() - 1;
  while (child > 0) {
    int parent = (child - 1) / 2;
    if (heap.get(parent).compareTo(heap.get(child)) >= 0) {
      break;
    }
    Collections.swap(heap, parent, child);
    child = parent;
  }
}

insert(…) 在保持完全二叉树形状的同时恢复最大堆序。

堆中不接受 null，否则比较操作没有定义。

固定容量实现需要先判断是否还有可用位置。

容量已满时不能继续追加，否则表示约束会被破坏。

新值先追加到数组末尾；这个位置唯一保持完全二叉树形状，随后从这个孩子位置开始上滤。

只要当前结点还不是根，就可能需要继续检查它与父结点的顺序。

0-based 表示中 parent=(child-1)/2，因此上滤每轮都沿唯一祖先边向上。

父结点已经不小于当前孩子时，当前路径满足最大堆序，可以停止。

一旦遇到合法父子关系，更高层原本就是合法堆，不需要继续比较。

否则交换父结点与孩子，并从新的孩子位置继续；每轮上移一层，所以最坏时间为 O(log n)。

删除堆顶：下滤过程

删除堆顶代码

T deleteMax() {
  if (isEmpty()) {
    throw new NoSuchElementException("heap is empty");
  }
  int last = size() - 1;
  Collections.swap(heap, 0, last);
  T maximum = heap.remove(last);
  if (!isEmpty()) {
    percolateDown(0);
  }
  return maximum;
}

private void percolateDown(int parent) {
  while (parent * 2 + 1 < size()) {
    int child = parent * 2 + 1;
    if (child + 1 < size() && heap.get(child + 1).compareTo(heap.get(child)) > 0) {
      child++;
    }
    if (heap.get(parent).compareTo(heap.get(child)) >= 0) {
      break;
    }
    Collections.swap(heap, parent, child);
    parent = child;
  }
}

deleteMax() 删除根，同时保持完全二叉树形状和最大堆序。

空堆没有可删除的根，因此先检查边界。

删除空堆没有合法返回值，直接抛出异常。

先定位最后一个元素，把它与根交换，再删除末尾；这样结构始终保持连续的 0-based 前缀。

若删除后仍有元素，新的根可能破坏堆序。

从下标 0 开始下滤，只修复一条根到叶路径。

最大值已经被移出堆，返回它不会再影响剩余结构。

percolateDown(parent) 从一个可能过小的父结点开始恢复最大堆。

只要存在左孩子，当前父结点就还可能继续向下交换。

0-based 表示的左孩子是 2*parent+1。

右孩子存在时，需要比较两个孩子，选出更大的那个。

较大的孩子才是最可能违反最大堆序的方向。

若父结点已经不小于最大孩子，这一层以及更深处都不需要再修复。

满足堆序后即可停止下滤。

否则交换父结点与较大孩子，并继续向下一层；每轮下降一层，所以最坏时间为 O(log n)。

下滤代码

private void percolateDown(int parent) {
  while (parent * 2 + 1 < size()) {
    int child = parent * 2 + 1;
    if (child + 1 < size() && heap.get(child + 1).compareTo(heap.get(child)) > 0) {
      child++;
    }
    if (heap.get(parent).compareTo(heap.get(child)) >= 0) {
      break;
    }
    Collections.swap(heap, parent, child);
    parent = child;
  }
}

percolateDown(parent) 修复从一个可能过小的父结点开始的局部违例。

只要存在左孩子，当前结点就还可能继续下滤。

0-based 数组中左孩子位置为 2*parent+1。

若右孩子存在，先比较两个孩子，选出更大的那个。

较大的孩子决定本层最严格的最大堆约束。

父结点已经不小于最大孩子时，当前子树重新满足堆序。

满足条件后可以立即停止，不需要继续访问更深结点。

否则交换父结点与较大孩子，并沿同一路径继续向下；每轮下降一层，最坏为 O(log n)。

单次操作复杂度

堆高为：

\[ \lfloor \log_2 n \rfloor \]

因此：

操作	时间
`max()`	\(O(1)\)
`insert()`	\(O(\log n)\)
`deleteMax()`	\(O(\log n)\)

建堆

建堆方法一：逐个插入

逐个插入 \(n\) 个元素。

每次插入最坏 \(O(\log n)\)。

总时间：

\[ O(n\log n) \]

这种方法简单，但不是最优建堆。

建堆方法二：Floyd 建堆

Floyd 建堆代码

把所有元素先放入数组，再从最后一个内部结点开始下滤：

static <T extends Comparable<? super T>> MaxHeap<T> initialize(List<T> values) {
  MaxHeap<T> heap = new MaxHeap<>(Math.max(values.size(), 1));
  for (T value : values) {
    heap.heap.add(Objects.requireNonNull(value, "heap element"));
  }
  for (int parent = heap.size() / 2 - 1; parent >= 0; parent--) {
    heap.percolateDown(parent);
  }
  return heap;
}

initialize(…) 先建立完全二叉树形状，再自底向上恢复最大堆序。

容量至少为 1 只是为了构造容器；逻辑元素仍完全由实际数组长度决定。

先把输入按原顺序连续放入数组，树形因此已经正确。

叶子没有孩子，天然满足堆序，不需要额外处理。

0-based 数组最后一个内部结点是 size/2-1，从这里向下标 0 逆序处理。

处理父结点时，它的孩子子树已经是堆；一次下滤即可把当前子树修好。

所有内部结点完成后整棵树成为最大堆；底层结点多但移动距离短，因此 Floyd 建堆总时间为 O(n)。

Floyd 建堆复杂度

靠近叶子的结点很多，但下滤距离短。

靠近根的结点少，虽然下滤距离长。

总工作量为：

\[ \sum_{h\ge 0} \frac{n}{2^{h+1}}h = O(n) \]

因此 Floyd 建堆是线性时间。

堆排序

堆排序流程

堆排序流程：

将 \(n\) 个元素建成最大堆
把堆顶最大值与当前堆区末尾交换，并把该末尾位置移入已排序后缀
对新的堆顶下滤，恢复剩余前缀的最大堆不变量；重复直到堆区只剩一个元素

复杂度：

\[ O(n)+nO(\log n)=O(n\log n) \]

堆排序原地，但不稳定。

为什么堆排序不稳定

稳定排序要求相等关键字保持原相对顺序。

堆排序中，元素会沿树路径与远处元素交换。

相同关键字可能跨越彼此，因此堆排序通常不稳定。

典型应用

第 K 大元素：问题描述

给定数组：

\[ [3, 5, 8, 9, 1, 10] \]

要求：找出第 \(3\) 大元素。

排序后从大到小是：

\[ 10, 9, 8, 5, 3, 1 \]

所以答案是 8。

但是回答这个问题不需要全量排序。只用本章的优先队列工具，怎样只维护与答案有关的候选，而不是把所有元素完全排好序？

第 K 大元素：思路分析

方法1：全量最大堆

从所有元素建最大堆
连续执行 \(k\) 次 deleteMax
第 \(k\) 次取出的就是第 \(k\) 大元素

方法2：大小 k 的最小堆

从前 \(k\) 个元素建一个最小堆
逐个比较后续元素与堆顶门槛
只有新元素大于堆顶时，才替换根并恢复最小堆
扫描结束后，堆顶就是第 \(k\) 大元素

第 K 大元素：复杂度比较

方法 2 的初始 \(k\) 个元素既可以逐个 offer（简单、整体仍为 \(O(n\log k)\)），也可以先放入数组再用 Floyd 在 \(O(k)\) 时间建堆；下面的复杂度对比采用后者。

第 K 大元素：最小堆过程

\[ [3, 5, 8, 9, 1, 10] \]

第 K 大元素：代码 1——主流程

static int kthLargest(int[] values, int k) {
  if (k <= 0 || k > values.length) {
    throw new IllegalArgumentException("k out of range");
  }
  PriorityQueue<Integer> smallestOfTopK = new PriorityQueue<>(k);
  for (int value : values) {
    if (smallestOfTopK.size() < k) {
      smallestOfTopK.offer(value);
    } else if (value > smallestOfTopK.element()) {
      smallestOfTopK.remove();
      smallestOfTopK.offer(value);
    }
  }
  return smallestOfTopK.element();
}

kthLargest(…) 只保留当前最大的 k 个候选；最小堆根就是第 k 大阈值。

最小堆的角色不是“把前 k 个数排好”，而是把当前前 K 大候选中最弱的元素放在根，形成可在 O(1) 时间读取的门槛。真正把堆大小限制在 k 的是后面的控制逻辑，而不是 Java PriorityQueue 的初始容量参数。

扫描任意前缀后维持不变量：若已看过的元素少于 k，堆保存全部元素；否则堆中恰好是该前缀最大的 k 个值。只有新值超过根这个门槛时，候选集合才需要更新。

扫描结束时堆中就是全局最大的 k 个元素，而最小堆根是这 k 个元素中最小的一个，也就是第 k 大。时间 O(n log k)、额外空间 O(k)；当 k 远小于 n 时，优势来自始终只维护 k 个候选。

第 K 大元素：代码 2——Floyd 建最小堆

static void buildMinHeap(int[] heap) {
  for (int parent = heap.length / 2 - 1; parent >= 0; parent--) {
    percolateDownMin(heap, parent, heap.length);
  }
}

static void percolateDownMin(int[] heap, int parent, int size) {
  if (size < 0 || size > heap.length || parent < 0 || (size > 0 && parent >= size)) {
    throw new IllegalArgumentException("invalid heap range");
  }
  while (parent * 2 + 1 < size) {
    int child = parent * 2 + 1;
    if (child + 1 < size && heap[child + 1] < heap[child]) {
      child++;
    }
    if (heap[parent] <= heap[child]) {
      break;
    }
    int temp = heap[parent];
    heap[parent] = heap[child];
    heap[child] = temp;
    parent = child;
  }
}

buildMinHeap(…) 用 Floyd 的自底向上顺序把 0-based 数组整体变成最小堆。

最后一个内部结点是 length/2-1；从这里向下标 0 处理，叶子无需单独下滤。

处理父结点时，它的孩子子树已经是最小堆，因此一次下滤即可修好当前子树；总建堆成本为 O(k)。

percolateDownMin 从一个可能过大的父结点开始，沿一条根到叶路径恢复最小堆序。

size 划定本次有效堆区，所有比较和交换都只能发生在这个前缀内。

只要左孩子存在，当前父结点就还有继续下滤的可能。

0-based 数组的左孩子是 2*parent+1。

右孩子存在时选择更小的孩子，因为它给出本层最严格的最小堆约束。

若父结点已经不大于最小孩子，当前子树恢复合法，可以立即停止。

否则交换父结点与较小孩子并继续向下；每轮下降一层，所以单次下滤为 O(log k)。

第 K 大元素：代码 3——最小堆下滤

static void percolateDownMin(int[] heap, int parent, int size) {
  if (size < 0 || size > heap.length || parent < 0 || (size > 0 && parent >= size)) {
    throw new IllegalArgumentException("invalid heap range");
  }
  while (parent * 2 + 1 < size) {
    int child = parent * 2 + 1;
    if (child + 1 < size && heap[child + 1] < heap[child]) {
      child++;
    }
    if (heap[parent] <= heap[child]) {
      break;
    }
    int temp = heap[parent];
    heap[parent] = heap[child];
    heap[child] = temp;
    parent = child;
  }
}

percolateDownMin(…) 从一个可能过大的父结点开始恢复最小堆序。

size 划定当前有效堆区；所有比较与交换都只能发生在这个前缀内。

只要左孩子存在，当前父结点就仍可能需要继续下滤。

0-based 数组中左孩子是 2*parent+1。

若右孩子存在，先从两个孩子中选出更小的那个。

父结点已经不大于最小孩子时，本层满足最小堆序，可以立即停止。

若父结点更大，则交换父结点与较小孩子，把唯一的局部违例向下一层移动。

每轮严格下降一层，所以一次修复最多经过树高；用于维护前 K 大元素时，单次更新为 O(log k)。

应用：塔防游戏的离散事件引擎

塔防游戏里，很多行为都不是“立刻发生”，而是约定在未来某个时间触发。

塔在冷却结束后再次攻击
敌人在未来到达下一个路口
中毒效果每隔 1 秒结算一次
下一波敌人在指定时间开始生成

事件队列不是只出堆

离散事件引擎维护的是 所有已知的未来事件。每轮循环先 deleteMin 取出最早事件，执行后可能立刻 insert 新事件。

一段完整的事件流

下面为了讲清时间关系，把未来事件按时间展开成概念列表；这不是堆的数组形状。真实最小堆只保证堆顶是最早事件，并不保证其余位置全局有序。重点观察：事件会出堆，也会从内部逻辑或外部输入入堆。

本章小结

优先队列抽象数据类型的关键语义是插入任意元素，并反复访问或删除当前最高优先级元素。
无序线性表插入便宜、删除极值昂贵；有序线性表相反；堆在两类操作之间取得对数级折中。
最大堆和最小堆都依赖完全二叉树数组表示，父子下标公式把树结构压进连续存储。
插入通过上滤恢复堆序，删除堆顶通过下滤恢复堆序；每次只沿一条根叶路径移动。
Floyd 建堆从最后一个非叶结点向前下滤，总成本是 \(O(n)\)，不是 \(O(n\log n)\) 的简单相乘。
堆排序原地但不稳定，因为下滤和堆顶交换可能改变相等关键字的相对次序。
第 K 大元素问题不需要全量排序，可用大小始终不超过 \(K\) 的最小堆只保留当前前 K 大候选集合。

下载本章完整 Gradle 工程

本章习题

习题 1：最小堆插入 3：已知序列： \(5,8,12,19,28,20,15,22\) 是最小堆，插入 \(3\)。
习题 2：判断是否为堆：判断数组 \([91,72,84,65,50,61,80,30,42]\) 是否为最大堆，并说明需要检查哪些结点。
习题 3：堆排序复杂度：分析堆排序的建堆阶段和重复删除堆顶阶段，求总时间复杂度、额外空间复杂度，并判断稳定性。

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦

第 6 章 优先队列

引入