这一篇在干嘛？
vector 扩容一次 ，凭什么说 push_back 是摊还 ？本章把这类”单次贵、序列便宜”的论证系统化成三种方法——聚合、核算（记账）、势能，并用来兑现斜堆、斐波那契堆、伸展树这些”没有最坏保证、只有摊还承诺”的数据结构的性能诺言。
11.1 先热身：一个不相干的谜题
一个 64 格棋盘放麦粒：第 1 格 1 粒、第 2 格 2 粒、每格翻倍。总粒数 ——单格（后期）放得多，但平均每格 1 粒的成本被前期的少摊平了。摊还分析的精神一样：看序列总账，不看单笔支出。
三个术语约定：
- 摊还时间：序列总代价 / 操作数（上界形式）。
- 聚合分析：直接算 N 次操作的总代价 ，摊还 = 。
- 核算（记账法）：给便宜操作”多收钱”存进账户，贵操作从中取用——账户永不透支即可。
聚合法第一例（vector 扩容）：N 次 push_back，搬家总代价 ，加上 N 次本身的代价，总 ，摊还 。
11.2 二项队列的摊还分析
二项队列（第 6 章）insert 最坏 （全队列进位），但多数插入只碰一棵树。用核算法：
- 收费规则：每次 insert 收 2 个时间单位——1 个用于实际插入，1 个”存起来”作为未来进位的存款。
- 账户：对每棵高度为 h 的树，要求它存有 1 个单位（保证其”可被进位搬运”）。
- 验证：插入首建 花 1 存 1；合并/进位时，两棵 合并成 花 1 个单位，但新树的”存款”继承两棵旧树各 1 的存款（多退少补后账户仍不透支）。
结论（定理 11.1）：N 次插入总代价 ，摊还 ——与二进制计数器 +1 的期望常数一致。
白话：便宜的操作交”保险费”，贵的进位操作花的是保险费，不是现钱。只要任何时刻总存款 ≥ 未来义务，总账就是便宜的。
11.3 斜堆（Skew Heap）：无序性的摊还胜利
斜堆 = 左式堆的”懒人版”：merge 时无条件交换左右孩子（不检查 npl）。单次 merge 最坏 ，但摊还 （定理 11.2）——用势能法证明：
势能函数 = 重的节点数（heavy node：右子树节点数 > 总节点数一半的节点）。
证明骨架：merge 走右路径（ 个右节点），其中轻节点 merge 后变重（势能 +1，由摊还代价预付），重节点 merge 后必然变轻（势能 −1，抵消实际代价）。增减相抵，总摊还 。
白话：势能法 = “状态欠账函数”。实际代价 = 摊还代价 − 势能变化。选一个能反映”结构恶化程度”的势能（这里是重节点数），就能把昂贵操作的账算到便宜操作头上。难点全在挑对势能函数——这是三种方法中最强大也最考验直觉的。
11.4 斐波那契堆：为 Dijkstra 减负而生
动机：Dijkstra 需要 decreaseKey。二叉堆每次 ；斐波那契堆把 decreaseKey 摊还做到 ，deleteMin 摊还 ——稀疏图最短路的总代价降到 。
核心机制（懒惰策略）：
- 惰性合并：insert 只是把新树扔进根列表，不合并（O(1)）；代价是根列表越来越乱，账留给 deleteMin 还。
- 切枝（cascading cut）：decreaseKey 直接把孩子剪下来扔进根列表（O(1)），不再上滤。为防无限制剪枝，节点失去第一个孩子时打”丢失标记”；失去第二个孩子时自己也被剪走，连锁上溯。
白话：斐波那契堆 = “先欠着，结账时一起算”。所有便宜操作都 （因为都只是”记账”），昂贵的整理全部推迟到 deleteMin 一次性完成。理论最优，实践中常数大、实现复杂，通常只有输入规模巨大且 decreaseKey 频繁时才划算（竞赛圈常用配对堆替代）。
11.5 伸展树的摊还分析（呼应第 4 章）
第 4 章承诺”摊还 “，证明用的正是势能法：（各节点子树大小的对数和，即”排名和”）。zig/zig-zag/zig-zig 三种旋转各有代价与势能变化的固定不等式， telescoping（望远镜求和）后单次摊还 ≤ 。
白话：伸展操作的巧劲在 zig-zig（先旋父亲再旋祖父）——它让”一条长链被展开”的过程释放大量势能，正好支付旋转的开销。若改成”旋转父子”的朴素版，势能法会失效，这正是第 4 章说”简单想法行不通”的数学原因。
11.6 三种方法怎么选
| 方法 | 一句话 | 适用 |
|---|---|---|
| 聚合 | 直接算序列总账 | 代价模式规律（vector 扩容） |
| 核算 | 给操作定价，多收存钱 | 代价可预存（二项队列进位） |
| 势能 | 定义结构恶化的”欠账函数” | 结构动态变化（斜堆/伸展树/斐波那契堆） |
常见坑
① 摊还界当最坏界用：斜堆单次 merge 最坏 是真的，“摊还 O(log N)“只约束序列总账——实时系统别用斜堆。② 势能函数随便挑：必须保证初始势能有限、任意时刻 ≥ 0（否则”透支”证明作废）。③ 记账法忘了验证账户下界：只需找到一个时刻账户为负，整个证明崩塌。
通关标准
学完本篇你应该能做到：① 用聚合法证明 vector/哈希表扩容摊还 O(1)；② 用记账法复述二项队列 insert 摊还 O(1) 的收费方案；③ 陈述势能法框架（实际=摊还−ΔΦ）并解释势能函数的非负性要求；④ 说清斐波那契堆凭什么把 decreaseKey 做到 O(1)、以及它对 Dijkstra 的意义。
摊还复杂度和平均复杂度有什么本质区别？
平均复杂度是对输入分布取期望（依赖输入随机性）；摊还复杂度是对任意输入序列的总代价上界（确定性成立）。快排的 O(N log N) 是平均，斜堆的 O(log N) 是摊还。
为什么二项队列 insert 每次收 2 个时间单位就够了？
1 单位付本次插入，1 单位存作”这棵树未来参与进位”的预付款。进位链每前进一层恰好消费存款而非现钱，故任意操作序列账户不透支。
斐波那契堆 decreaseKey 的"第二刀"规则是什么？为什么需要？
节点失去第 1 个孩子只打标记；失去第 2 个孩子时它自己也被剪下并连锁上溯。没有这条规则，一个节点可以被无限剪孩子、子树规模塌缩，deleteMin 的 O(log N) 保证随之崩溃。
势能法中"实际时间 = 摊还时间 − 势能变化"怎么理解？
把每个操作多收的费（摊还−实际）存进势能池；实际时间便宜的操作给池子充值，贵的从池子取钱。对序列求和，势能首尾只差有限值，总实际代价 ≤ 总摊还代价。
伸展树为什么必须用 zig-zig（先旋父再旋祖）而不是逐对旋转？
势能证明显示 zig-zig 让路径上的势能大幅下降（长链被”对折”展开），释放的势能支付昂贵旋转；逐对旋转释放的势能不足，摊还界退化。这也解释了伸展树实现的”怪异”细节。