第06章 优先队列（堆）：从二叉堆到左式堆

这一篇在干嘛？

很多场景只关心”当前最小/最大”：任务调度取最高优先级、Dijkstra 取最近节点、事件模拟取最早事件——全排序是浪费。优先队列（priority queue）把”取最值 + 插入”做到 $O(\log N)$、建堆做到 $O(N)$，是第 7 章堆排序和第 9 章图算法的引擎。

6.1 模型与朴素实现的代价

优先队列 ADT 至少两个操作：insert（插入）、deleteMin（取出并删除最小元，也常做 deleteMax 版）。

朴素实现的两难：有序数组——deleteMin $O(1)$ 但 insert 要找位 $O(N)$；无序数组——insert $O(1)$ 但 deleteMin 要全扫 $O(N)$。鱼与熊掌的解法就是堆。

6.2 二叉堆：两条性质撑起一切

结构性：完全二叉树——除最后一层外全满，最后一层从左到右填充。这带来一个决定性优化：不需要指针，用数组就能存树。位置 $i$ 的孩子是 $2i$ 和 $2i+1$，父亲是 $\lfloor i/2\rfloor$（下标从 1 开始）。

堆序性：每个节点 ≤ 它的两个孩子（小根堆）。注意：只保证父≤子，兄弟和跨子树之间无序——所以”找第 2 小”不能 $O(1)$，堆不是排序结构。

白话：堆是”家家都不过孩子”的家族——每家家长都比自家孩子小，但两家孩子谁大谁小没有结论。完全二叉树 + 数组 = 最省内存的树表示（无指针开销、缓存友好）。

insert：上滤（percolate up）

新元素先放到最后一个位置（洞），然后与父亲比较：比父亲小就把父亲拉下来（不是自己上移），继续向上直到父亲 ≤ 自己。

void insert(const Comparable &x) {
    array.push_back(std::move(x));   // 建洞
    int hole = theSize;
    while (hole > 1 && x < array[hole / 2]) {   // 还没到根且父亲更大
        array[hole] = std::move(array[hole / 2]); // 父亲下来填洞
        hole /= 2;                                 // 洞上移
    }
    array[hole] = std::move(x);      // 洞停在合适位置，x 入座
}

白话：插入像新员工”往上漂”——只跟直接领导比，领导大就换位。最多爬 $\lfloor \log N\rfloor$ 层，$O(\log N)$；而且实际往往提前结束（平均 2.6 次比较，随机数据下大多数元素本来就沉在低层）。

deleteMin：下滤（percolate down）

根就是最小元，取走后剩个洞。策略：把最后一个元素搬到洞，然后向下渗透——与两个孩子中较小的交换，直到两个儿子都 ≥ 它。

void percolateDown(int hole) {
    int child;
    Comparable tmp = std::move(array[hole]);   // 待下滤元素
    for (; hole * 2 <= theSize; hole = child) {
        child = hole * 2;
        if (child != theSize && array[child + 1] < array[child])
            ++child;                            // 选较小的儿子
        if (array[child] < tmp)
            array[hole] = std::move(array[child]); // 小儿子上来
        else
            break;
    }
    array[hole] = std::move(tmp);
}

白话：末位元素”空降”到顶后会一路下沉，每层跟”两个孩子中较小者”换位，保证换上来的永远不比换下去的大。$O(\log N)$。

buildHeap：O(N) 的魔法

拿到乱序数组，从最后一个非叶节点到根逐个 percolateDown。直觉上每个节点下滤最贵 $O(\log N)$、共 $N$ 个节点，像 $O(N\log N)$——实际是 $O(N)$：

${\sum }_{h=0}^{\lfloor \log N\rfloor }\frac{N}{2^{h+1}}\cdot h<N{\sum }_{h=0}^{\infty }\frac{h}{2^h}=O(N)$

白话：低层节点多但下滤近（树的高层节点少、下滤贵——两者相乘求和被 $2^h$ 压住）。堆排序、Dijkstra 初始化都靠免费建堆。注意：逐个 insert 建 N 元堆是 $O(N\log N)$，和 buildHeap 的 $O(N)$ 不是一回事。

其他操作

decreaseKey（降值后上滤）、remove(p)（降到 $-\infty$ 再 deleteMin）、findMin $O(1)$、increaseKey 下滤。

6.3 应用一：选择问题（找第 k 大）

• 算法 6A：全部建堆后 deleteMin k 次——$O(N+k\log N)$，对 $k=\lfloor N/2\rfloor$（中位数）即 $O(N)$。
• 算法 6B：维护一个只装 k 个元素的大根堆，流式处理：新元素比堆顶大就替换。$O(N\log k)$，内存只装 k 个元素——海量数据 Top-K 的标准解法。

6.4 应用二：事件模拟

银行排队模拟：事件（到达/离开）按时间排序处理，但新事件动态产生——优先队列天然匹配：deleteMin 取最早事件，处理产生的新事件 insert 回去。

6.5 d 堆：孩子多一点，插入快一点

完全 d 叉树：insert 上滤深度 ${\log }_{d}N$ 更浅（插入快），deleteMin 要在 d 个孩子里找最小（找最值慢）。插入多、合并少的场景用大 d（如 $d=4$）有实测优势。

6.6 左式堆：支持 O(log N) 合并

二叉堆的 merge 很难做（数组表示没法高效拼两棵树）。**左式堆（leftist heap）**用指针表示，专攻合并。

零路径长（null path length, npl）：从节点出发到最近一个”不足两孩子的节点”的最短路径长；空节点 npl = −1。

左式性质：每个节点左孩子的 npl ≥ 右孩子的 npl（左重右轻）。

白话：左式堆把”重活”偏置到左边，右边天然很浅（可证右路径至多 $O(\log N)$）。合并只在右路上做，复杂度就有了保证。

合并算法（递归版）：

LeftistNode *merge(LeftistNode *h1, LeftistNode *h2) {
    if (h1 == nullptr) return h2;
    if (h2 == nullptr) return h1;
    if (h1->element > h2->element)
        std::swap(h1, h2);                    // 保证 h1 根小，当新根
    if (h1->left == nullptr)                  // 左空直接挂
        h1->left = h2;
    else {
        h1->right = merge(h1->right, h2);     // 右子树递归合并
        if (h1->left->npl < h1->right->npl)   // 左轻则交换，恢复左式性质
            std::swap(h1->left, h1->right);
        h1->npl = h1->right->npl + 1;
    }
    return h1;
}

白话：小根当新根；把大根堆塞进小根的右子树里继续递归合并；回溯时检查左右”轻重”（npl），轻了就左右交换。整个过程沿右路径进行，$O(\log N)$。insert = 与单节点堆 merge；deleteMin = 取根后 merge 左右子堆。

6.7 二项队列：三操作全对数的均衡派

二项树 $B_k$：$B_0$ 单节点；$B_k$ 由两棵 $B_{k-1}$ 合并而成，恰有 $2^k$ 个节点、高 k。二项队列 = 二项树的森林，且每种高度至多一棵——于是”森林的二进制表示”：

• insert ≈ 二进制 +1，二项树”进位合并”（两棵同高 $B_k$ 合并成一棵 $B_{k+1}$），最坏 $O(\log N)$、摊还 $O(1)$。
• merge ≈ 二进制加法（带进位），$O(\log N)$。
• deleteMin：找到最小的根（$O(\log N)$ 扫描森林），删掉它后其孩子恰好构成一个二项队列，与剩余部分 merge。

白话：二项队列把”堆结构”和”二进制计数”对上了——加法就是合并，减一位就是删最小元。三操作全部 $O(\log N)$，比二叉堆（merge 不行）和左式堆（insert 最坏 O(log N)）更均衡；代价是实现复杂。

选型速查：只要 insert/deleteMin → 二叉堆（数组，最简单最快）；要 merge → 左式堆（或斜堆，第 11 章摊还分析）；三操作都要对数保证 → 二项队列（或第 12 章的配对堆——实践更快但理论略弱）。

常见坑

① deleteMin 下滤选错孩子：必须与较小的孩子交换，选错了堆序就破了。② 以为堆能 O(1) 找第 k 小：堆只有父子有序，兄弟无序，找第 k 小要借辅助结构。③ 把逐个 insert（O(N log N)）当成 buildHeap（O(N)）：数组初始化场景一定要用 buildHeap。

通关标准

学完本篇你应该能做到：① 手推 insert 上滤与 deleteMin 下滤的每一步交换；② 证明 buildHeap 是 O(N)；③ 用堆解 Top-K 问题并说清为什么装 k 个元素的堆是 O(N log k)；④ 手写左式堆 merge 并解释 npl 与左式性质如何保证右路径 O(log N)；⑤ 用二进制类比说清二项队列的 insert/merge/deleteMin。

为什么二叉堆可以用数组表示而不用指针？

完全二叉树的形状被”层序填满”唯一确定，父/子下标关系（i、2i、2i+1）是算术关系，无需指针。省内存且对缓存友好。

buildHeap 为什么是 O(N) 而不是 O(N log N)？

高度 h 的节点恰有约 N/2^(h+1) 个，每个下滤最多 h 步，总代价 Σ N/2^(h+1)·h ≤ N·Σ h/2^h = 2N。贵的下滤只发生在极少数高层节点上。

Top-K 问题为什么维护大根堆装 k 个元素，而不是小根堆？

要”最大的 k 个”：用大根堆装”候选的最小 k 个”会让替换判断变难。正确做法是小根堆装当前 k 个最大候选，堆顶是这 k 个里的最小者，新元素比堆顶大就替换——一次比较完成淘汰。

左式堆的 npl 是什么？它如何保证合并的复杂度？

npl 是到最近”缺孩子节点”的最短路径。左式性质（左 npl ≥ 右 npl）迫使右路径不超过 O(log N)；merge 沿右路径递归，故 O(log N)。

二项队列里 insert 的摊还 O(1) 怎么理解？

与二进制计数器 +1 同构：多数插入只碰 B₀（O(1)），碰 B₁、B₂…… 的概率逐级减半，期望碰的树数量是常数级（1+1/2+1/4+…=2）。