2.4 Priority Queues：二叉堆、动态极值与堆排序

2.4 · Priority Queues覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“2.4 · Priority Queues”如何以二叉堆的形状和次序不变量连接动态极值、上浮下沉与堆排序
能逐项核对优先队列、优先队列API、初级实现、二叉堆、堆操作、堆排序，并区分作者站内容与本页独立补充
能按“parent(k)=floor(k/2)，children(k)=2k,2k+1；插入与删除最大值均为 O(log N)”手算一个最小输入，逐步检查“对每个 k>1 都有 heap[parent(k)]≥heap[k]，有效元素仅位于 1..N”
能注入“sink 时仍访问已经缩短后的 N+1 槽位，或在两个孩子中选择较小者交换”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“2·4 · Priority Queues”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“2·4 · Priority Queues”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“2·4 · Priority Queues”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：2.4 · Priority Queues

1. 优先队列：在本页通过“把新键放到末尾”连接解释、交互状态和练习验收。
2. 优先队列API：在本页通过“沿父链上浮”连接解释、交互状态和练习验收。
3. 初级实现：在本页通过“交换根与末项”连接解释、交互状态和练习验收。
4. 二叉堆：在本页通过“沿较大孩子下沉”连接解释、交互状态和练习验收。
5. 堆操作：在本页通过“核对堆序与输出”连接解释、交互状态和练习验收。
6. 堆排序：在本页通过“把新键放到末尾”连接解释、交互状态和练习验收。

从“只要当前最大项，不要全排序”开始

优先队列（priority queues）服务于“边收集边处理最重要项”的场景。Job scheduler收到新任务后取最高priority，event simulation取最早time，TopM client只保留最大的M条transaction；这些问题若每次都重排所有items，会做大量不需要的工作。

先预测维护一个变量 maxSoFar 是否足以支持删除最大项。第一次max可以常数返回，但删除后必须从剩余items重新发现下一最大，除非另外维护结构。优先队列的难点不是看见当前maximum，而是在insert与delMax交错时持续维护它。

官方2.4按 Priority queue API、Elementary implementations、Heap definitions、Algorithms on heaps、Heap-based priority queue、Practical considerations、Heapsort 展开。抽象API决定observable behavior，binary heap只是让insert和delete extreme都快的一种representation。

2.4.1 Priority queue API：动态极值而非全序容器

优先队列API（priority queue API）对max-oriented queue的核心是：

MaxPQ()
MaxPQ(int capacity)
void insert(Key key)
Key max()
Key delMax()
boolean isEmpty()
int size()

Generic Key遵守Comparable total order；也可由Comparator注入顺序。Duplicate maximum存在时，API可返回任意一个largest-key record，除非另行声明stability或tie-break。Empty max/delMax 应抛明确异常，null key通常拒绝，不能返回null同时表示“empty”和“合法key”。

TopM 使用minimum-oriented PQ限制size为M：每读一条transaction就insert；若size超过M就delMin；最终得到largest M。这个client说明方向选择取决于保留策略：为了保留最大M，内部反而不断淘汰minimum。

2.4.2 Elementary implementations：把线性成本放在哪一端

初级实现（elementary implementations）直接复用stack与selection/insertion sort思想：

Unordered array尾插是Theta(1)，delMax需扫描N项后与尾项交换，Theta(N)。
Ordered array插入要移动items保持顺序，Theta(N)，max与delMax在末端，Theta(1)。
Unordered linked list头插constant，delete max需linear scan并维护predecessor。
Reverse-ordered linked list插入linear，delete max从head unlink constant。

若workload几乎全是insert而极少delMax，无序array可胜过heap；若大量max查询而更新少，有序表示可能更合适。Binary heap的价值是两种mutating operations都保证logarithmic，不是所有workload都常数最优。

2.4.3 Binary heap：complete shape加partial order

二叉堆（binary heap）结合两个约束。Shape是complete binary tree，除最后一层外全满、最后层从左填；order是每个parent key不小于children。它不是binary search tree：siblings无序，左subtree与右subtree之间没有全序关系。

Official max heap使用 pq[1..n]，pq[0] 留空。对index k：

parent(k)=\left\lfloor\frac{k}{2}\right\rfloor, \qquad left(k)=2k, \qquad right(k)=2k+1

Heap order（heap order）立即推出root是maximum，但不能推出minimum位置；minimum可能在任一leaf，查找仍需Theta(N)。Complete shape使height：

h=\lfloor\lg n\rfloor

Array无需存child pointers，size n就隐含shape。Certificate可在linear time遍历所有parent-child edges；只检查root maximum不足以发现深层violation。

2.4.4 Heap operations：局部破坏，沿一路修复

堆操作（heap operations）先做一个可能破坏局部order的简单变更，再reheapify。因为变更只影响一条ancestor path，不需扫描全树。

Bottom-up reheapify swim(k) 处理新node比parent大的情况：

private void swim(int k) {
    while (k > 1 && less(k / 2, k)) {
        exch(k, k / 2);
        k = k / 2;
    }
}

每次exchange后，moving key与两个children的关系已正确，但可能仍大于新parent；到root或parent不小于它时结束。Insert先确保capacity，写到 pq[++n]，再swim。

Top-down reheapify sink(k) 处理root或internal node比child小的情况：

private void sink(int k) {
    while (2 * k <= n) {
        int j = 2 * k;
        if (j < n && less(j, j + 1)) j++;
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

必须与较大child交换。若选较小child，moving key可能仍小于另一个child，当前层order没有修复。DelMax保存root，根尾交换、令n减1、把旧tail slot设null避免loitering，再从root sink；capacity过大时可halve。

public Key delMax() {
    if (isEmpty()) throw new NoSuchElementException();
    Key max = pq[1];
    exch(1, n--);
    sink(1);
    pq[n + 1] = null;
    if (n > 0 && n == (pq.length - 1) / 4)
        resize(pq.length / 2);
    return max;
}

在n-item heap中，insert最多约 1 + lg n compares，delMax最多约 2 lg n compares：

C_{insert}(n)\le 1+\lg n, \qquad C_{delMax}(n)\le 2\lg n

2.4.5 Practical considerations：容量、key ownership与index

动态数组在full时double、size降到capacity四分之一附近时halve，保留hysteresis避免每次insert/delete来回resize。由于copy是linear，单次operation可能linear，但sequence amortized bound仍logarithmic dominated。

Client不应在item进入PQ后修改参与比较的key。Heap只在operations时局部修复；外部mutation可让child突然大于parent，结构对此毫无通知。解决方式是immutable keys、defensive copy，或提供显式changeKey并执行swim/sink。

索引优先队列（indexed priority queue）维护 pq[position]=clientIndex 与 qp[clientIndex]=position，再用keys保存priority。Every exchange必须同步更新pq和qp；否则contains、changeKey会操作错误item。Dijkstra shortest path后续正需要按vertex index降低key。

Multiway heap把branching factor改成d，height约为log_d N；swim层数变少，sink每层却要找d个children中的extreme。选择d要根据cache、comparison cost与operation mix测量，不能只看tree更矮。

2.4.6 Heapsort：在输入数组内复用heap

堆排序（heapsort）放弃PQ representation封装，直接把input array视为heap。它有两个phase：

Heap construction：从最后一个internal node向root逐个sink，建立max heap。
Sortdown：root与heap末尾交换，heap size减1，root sink；右侧sorted suffix逐项增长。

public static void sort(Comparable[] pq) {
    int n = pq.length;
    for (int k = n / 2; k >= 1; k--)
        sink(pq, k, n);
 
    int k = n;
    while (k > 1) {
        exch(pq, 1, k--);
        sink(pq, 1, k);
    }
}

Official Heap.java 对client array用offset helper模拟1-based indices。Sortdown invariant是 pq[1..k] 为max heap，pq[k+1..N] 已按升序固定，且heap中每项不大于sorted suffix首项。

Bottom-up heap construction是linear。高度r的node最多sink r层，而高node很少、低node很多；总exchanges可由height distribution界定：

\sum_{r\ge 0}\frac{N}{2^{r+1}}r < N

因此heapify少于N exchanges、至多约2N compares；若逐项insert建heap则是N log N上界，丢失这个结构性收益。完整heapsort少于约 2N lg N compares与exchanges，worst-case N log N，额外array space constant。

Heapsort不稳定，且array access locality通常不如quicksort；优势是原地且worst-case linearithmic。不能把heap priority queue的extra capacity与heapsort混淆：PQ为动态size维护独立array，heapsort直接复用input storage。

统一验收：从API序列到两阶段排序

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“2.4 · Priority Queues”的两个最小情境间切换，再逐项选择正式概念。预测“parent(k)=floor(k/2)，children(k)=2k,2k+1；插入与删除最大值均为 O(log N)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

2.4 · Priority Queues：对象、操作与不变量

以二叉堆的形状和次序不变量连接动态极值、上浮下沉与堆排序

选择最小情境

切换正式概念

插入极值: 向 [9,7,8,2,3] 依次插入 10
当前观察: priority queues：10 沿父链上浮到根，完全树形状不变

parent(k)=floor(k/2)，children(k)=2k,2k+1；插入与删除最大值均为 O(log N)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

优先队列：在实验 1 中指出对应状态，并写出一个通过条件。
优先队列API：在实验 2 中指出对应状态，并写出一个通过条件。
初级实现：在实验 3 中指出对应状态，并写出一个通过条件。
二叉堆：在实验 1 中指出对应状态，并写出一个通过条件。
堆操作：在实验 2 中指出对应状态，并写出一个通过条件。
堆排序：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“parent(k)=floor(k/2)，children(k)=2k,2k+1；插入与删除最大值均为 O(log N)”不是孤立结论？

问题 3：故障恢复。 怎样证明“sink 时仍访问已经缩短后的 N+1 槽位，或在两个孩子中选择较小者交换”已经修复？

本章回顾

Priority queue维护动态maximum/minimum，不要求其他items随时全序。
Unordered与ordered初级实现把linear成本分别放在delete或insert。
Binary heap是1-based complete heap-ordered tree，root直接给出maximum。
Insert尾插后swim，delMax根尾交换后sink，两者沿单一路径logarithmic。
Dynamic resizing、immutable keys与indexed inverse mapping属于必须明确的工程contract。
Heapsort先linear bottom-up heapify，再N log N sortdown，原地且worst-case linearithmic。
Heap只保证partial order；搜索minimum、稳定遍历或sorted iteration都需要额外工作。