堆与 priority_queue

这道题的原型是洛谷 P3378，那道题只有前三条。这里多了两样东西：

1. 「堆为空时输出 E」 —— 空堆是一个题目允许的状态，不是「不会发生」。 随手写的生成器最爱做的事就是替题目把它排除掉（第 27~34 章那条「顺手写法」）。
2. 最后那一行「把剩下的从小到大列出来」 —— 第 35、36 章那条「题面多问一句，对拍就多一条腿」的第三次现场。

⚠ 而这次的账和第 36 章不一样，得老实分两半写：

★★ 多问的那一句，在弱数据上顶得上把生成器调狠一个数量级（11 → 88、76 → 244）； 可数据本身够狠之后，它的边际价值就只剩 283 → 290 了。 「多要一行输出」不是万能药，它是给数据不够狠的时候兜底的 —— 这比第 36 章那个「0 → 300」更接近常态，所以两笔账都要摆出来。

15
2        → E   ★ 空堆查询
1 9
1 5
2        → 5
1 2
1 8
1 1      ★ 这个 1 要一路上浮两层才到根
2        → 1
3            删掉 1
3            ★ 这一次下沉要在两个儿子里挑小的那个
2        → 5
1 4
3            删掉 4
2        → 5
3            删掉 5

答案：E 5 1 5 5，最后一行 8 9。

• 第 1 步的空堆查询，是「忘了判空」的唯一现场；
• 第 7 步那个 1（比祖上两代都小），是「上浮只上一层」的现场；
• 第 10 步那次下沉右儿子比左儿子小，是「下沉只看左儿子」的现场；
• 而最后那一行 8 9，是「下沉边界差一」和「a[--sz]」唯一的现场 —— ★ 这两个 bug 的前五行输出一个字都不错。

正解维护的是一棵完全二叉树，把顺序信息一路攒下来。要是标准答案也维护一棵堆， 两份代码就是同一个思路写了两遍 —— 只能验出打字错误，验不出想法错误 （第 9、15、34、35、36 章那条）。

所以这一份什么都不攒：插入就是往后一放；要最小值就从头到尾扫一遍。

★ 两处刻意为之的「不占便宜」：

• 扫的时候一次 break 都没有（第 31 章：「找到第一个就 break」会让暴力假装自己不慢）；
• 删除用的是 erase（把后面整段往前搬），不许用「和末尾交换再 pop_back」那种小聪明 —— 那样就不是「什么都不攒」了，而且会打乱顺序，而最后那一行要按从小到大输出。

brute 慢的原因一句话：每次要最小值，都要把「谁最小」这件事从零算一遍。

于是很多人的第一反应是：那我维护一个有序数组不就行了？最小值永远在第 0 位，O(1)。

⚠ 实测（count.cpp 里那一行 sorted，n = 16 000）：

★★ 两个 O(n²) 的做法，烂在完全不同的地方。 linear 烂在比较（每次都要全扫），sorted 烂在移动（插一个数要把后面整段往后挪）。 有序数组只是把工作量从一列搬到了另一列，一个数量级都没省下来。

★ 而堆之所以能赢，是因为它两列同时是 O(log n) —— 它维护的不是「全序」，而是刚好够用的那点顺序：只保证「爸爸 ≤ 儿子」。 要什么就只维护什么，这是这一章真正的思想。

（sorted 那 20 万次比较是二分查插入位置来的 ≈ n log n； 翻倍比：linear 的比较 4.00、sorted 的移动 4.01，两个都是标准的平方。）

堆是一棵完全二叉树：除了最后一层，每层都填满，最后一层的点靠左排。 把它按层从上到下、每层从左到右编号 1, 2, 3, …，塞进一个数组：

下标 i 的左儿子 = 2i        右儿子 = 2i + 1        爸爸 = i / 2（整除）

⚠ 下标从 1 开始，这三个公式才这么干净（0 基要写成 2i+1 / 2i+2 / (i−1)/2，能用但难记）。 根本不需要指针，一个数组就是一棵树。

★ 那它有多高？数一数就完了：

第 0 层  1 个        累计 1
第 1 层  2 个        累计 3
第 2 层  4 个        累计 7
…
第 h 层  2^h 个      累计 2^(h+1) − 1

前 h+1 层一共 2^(h+1) − 1 个点，所以 n 个点的完全二叉树高度就是 ⌊log₂ n⌋。∎

★★ 请把它和上一章摆在一起看： 第 36 章那条 O(α(n)) 是均摊出来的，完整证明要用势函数分层，那一章明说了「不证」； 这一章这条界三行就数完了，而且它是最坏情况的界，不是均摊的。 两章的 log 长得很像，来路完全不同。

n = 2×10⁵ 时，这个高度只有 17。

a[++sz] = x;      // 完全二叉树的下一个空位只有一个，就是最后一格
up(sz);           // 再让它爬到该去的地方

为什么必须先放最后一格：完全二叉树的形状是死的，能加点的位置只有那一个。 先保住形状，再修顺序 —— 这是堆的两个不变量，任何一步都不能同时破坏两个。

void up(int i) {
    long long x = a[i];                      // ★ 空穴法：把它抱在手上
    while (i > 1 && a[i >> 1] > x) {
        a[i] = a[i >> 1];                    // 爸爸落到空穴里
        i >>= 1;
    }
    a[i] = x;                                // 放下
}

a[1] = a[sz--];   // 根被删了，形状要保住 —— 只能拿最后一格来填
if (sz) down(1);  // 再让它沉到该去的地方

void down(int i) {
    long long x = a[i];
    while ((i << 1) <= sz) {
        int c = i << 1;
        if (c < sz && a[c + 1] < a[c]) c++;  // ★ 两个儿子里挑**小**的那个
        if (a[c] >= x) break;                // 已经就位
        a[i] = a[c];
        i = c;
    }
    a[i] = x;
}

⚠ 那句「两个儿子里挑小的」是这一章最容易漏的一行，而且漏了不会报错： 下沉的目的是「把这一格换成它这棵子树里最小的」，只跟左儿子换的话， 右儿子可能比换上来的还小 —— 堆顶就不再是全局最小值了（第 13 步有现场）。

• up 每次 i → i/2，只往上走；
• down 每次 i → 2i 或 2i+1，只往下走。

两者走过的下标序列，都是树上一条从根到叶的路的一段 —— 长度不超过树高，也就是 ⌊log₂ n⌋。

★ 这就是整条证明。不需要均摊、不需要势函数、不需要「大多数时候很便宜」这种话 —— 它是每一次都成立的最坏情况界。（对比第 36 章：那里的 α 只在均摊意义下成立， 单独某一次 find 完全可以很贵。）

播一遍你会看到：

• 插入时高亮从最后一格往上，删除时从根往下 —— 无论哪种，它都是一条根到叶的路；
• 右上角的「累计比较」涨得非常慢：默认那 15 步一共只比了 16 次（上浮 8、下沉 8）；
• 把数据切到「★ 递减插入 12,11,…,1」那一档 —— 每个新来的数都要一路爬到根， 那是第 10 步要说的「上界唯一被顶紧」的时候；
• 再切到「⚠ 递增插入」和「⚠ 全都一样」两档 —— 上浮一步都不走， 因为判断是 a[爸爸] > x，相等就停。

⚠ 动画和 trace.cpp 在 check:viz 里是逐步对的：每一步走过的下标、 这一步比了几次、搬了几次、累计多少、以及那一刻的整个数组，全部逐字节比 （不只对最终答案 —— 第 21 章以来那条规矩）。

• 从 n/2 开始：下标大于 n/2 的格子没有儿子，它们本身就是合法的堆（一个点的树）。 ★ 一半的点白送 —— 这就是 O(n) 的来源。
• 倒着走：down(i) 要求它的两棵子树已经是堆了。 「依赖谁，就先填谁」——第 21、26、27、28 章那句话在这里第八次登场。

★ 为什么是 O(n)：一行级数就完了。 高度为 h 的点最多 `⌈n / 2^(h+1)⌉ 个，每个最多往下走 h 层：

Σ_{h≥0}  h · n / 2^(h+1)  =  (n/2) · Σ_{h≥0} h / 2^h  =  (n/2) · 2  =  n

（Σ h/2^h = 1/2 + 2/4 + 3/8 + … = 2，那个经典的级数。） 每层最多 2 次比较 ⇒ 比较次数 ≤ 2n。∎

★ 直觉版更好记：大多数点很矮。 真正要走 log n 层的只有根那一个点， 而离叶子只有一两层的点占了绝大多数 —— 「树高 log n」和「平均高度 O(1)」不矛盾。

默认那 12 个数（8 3 11 6 1 9 4 12 7 2 10 5）：

一个个 push 建出来的：  1 2 4 7 3 5 9 12 8 6 10 11      （19 次比较）
★ 自底向上建出来的：    1 2 4 6 3 5 11 12 7 8 10 9      （17 次比较）

★ 两个数组不一样 —— 它们是两棵不同的树，但都是合法的小根堆。 而把它们分别堆排序倒出来：完全相同（check:viz 里在十组数据上钉着这条）。

★★ 所以「建堆用了哪种方法」和「空穴法还是 swap」是同一类东西： 只影响开销、不影响答案，对拍原理上全都抓不到（第 36 章第四个盲区）。 想看见它们，只有一条路：换尺子，数次数。

本机实测（./genKth 5000000 k，n = 500 万）：

./genKth 5000000 10 > k.txt
/usr/bin/time -f "%e 秒  %M KB" ./heapKth < k.txt

★ 交叉点在 k ≈ 10 万（第 24 章「二进制拆分 vs 单调队列交叉点在 k ≈ 100」的同款分寸）：

• k 小的时候堆又快又省内存（内存差十倍：3.9 MB vs 42.8 MB）；
• k = n/2 时堆是三份里最慢的一份（1.19 秒），因为它那个 log k 已经等于 log n 了。

⚠ 但真正让堆不可替代的不是这张表，是它需要的条件最少：

★★ 它从头到尾只看每个数一眼，不需要回头。 快速选择做不到这件事 —— 它必须把整个数组抓在手里反复划分。 所以数据是一个个流过来、来了就扔（在线 / 数据流）的时候，只有堆能做。

顺带一个漂亮的数字：n = 500 万、k = 10 时，真正进过堆的只有 143 个数 （./heapKth cnt）—— 越往后「比守门员还小」越难发生。

★ 「哪个更快」不是唯一的问题，「它需要什么条件」同样是问题。

★★ 六个里有三个只错在一行上，而其中两行正是题面「多问的那一句」。 这不是巧合，是第 1 步那个设计的直接兑现。

点「运行 ▶」看结果

★★ 把输入里所有的数取负，交给正解跑，再把输出里所有的数取负 —— 和这一份逐字节相同。 （最大的 x 就是最小的 −x；最后那一行「从大到小」也正好是「从小到大」取负。） check:viz 里 300 轮钉着这条，一轮不差。

前十二条恒等式在第 23~28、34、35、36 章。这一条和它们的形状一样： 一个 bug 精确地解了另一道题 —— 而这一次那「另一道题」就是少写一个 greater<> 的后果。

⚠ 请注意它和第 36 章第十二条的区别：那一条两边是开销（跳步数相同）， 这一条两边是答案（逐字节相同，只是要先做一次取负）。

gen.cpp 带了十个档位（./gen 种子 档位），种子固定 1..300：

★ 档位 0 那个 0 是这一章的起点。 我随手写生成器时做了一件完全没过脑子的事： 堆空的时候就改成插入 —— 听起来很合理（「不然删什么呢」）， 可题面白纸黑字写着「堆为空时输出 E」。

★ 第 27~34 章那条「生成器里那个不假思索的顺手写法，会悄悄给数据加一条题目里没有的性质」， 这一章第九次。而这次加的那条性质是：「堆永远非空」。 写生成器前先问一遍：题目到底允不允许？我是不是替它做了主？

★ 档位 1 是第二记耳光：我照第 22 章的经验先把值域压到 [1,6]（那一章「值域小才是灵魂」）， 实测六列全线下降（88 → 47 最惨）。原因在第 10 步已经量过了： 值一并列，下沉那句 a[c] >= x 立刻 break，路径变短，堆根本长不起来。

★ 档位 4 和 5 那两列刺眼的下降，是这张表最值钱的地方，下一张表见分晓。

• 档位 4（允许空堆）单独加的账要老实写：它把「忘了判空」从 0 抬到 171， 代价是另外五列一起掉（56→45、46→31、88→65、244→209、255→218）。

  ★ 第 30 章那条：把 0 变成非 0，掉多少抓获率都划算 —— 0 / 300 是「完全测不到」，171 / 300 是「第 2 轮就抓住」，两者不是量的差别。

• 档位 5（多删）单独加是全场最差的一档（31 / 25 / 62 / 209 / 0 / 224）， 可它加在档位 6 上是 161 → 278。 道理其实很直白：序列不够长时多删只会让堆一直空着（空堆上谁都输出 E， 第 31 章那条「某一支占得太多会吃掉别人」）；序列够长了，多删才等于让堆的形状多变几次形。

  ★★ 第 32、34、35、36 章那条「调优不可加：一处改动值不值得留，取决于其它旋钮此刻在哪」 的第五次，而且这次和第 36 章那次一模一样刺眼：一处单独看是负分的改动，最后被留下了。

• 档位 2（值域拉开）单独加几乎一个数没变（56→58、46→41、88→81）， 加在档位 7 上却是 278 → 290。同一条规律的另一面。
• 档位 9 是在最终环境里重新量「值域压小」（第 34、35 章那条）：290 → 224， 在裸环境里有害，在最终环境里还是有害 —— 撤回。 ⚠ 但它值得留成一个档位：「有害」这件事也要可复现。

★ 最后定档的标准照旧：让最弱的那一支尽量强（不是平均分最高）—— 最弱的一直是 wrongLast，档位 8 把它顶到了 290。

【1】★★ 一棵完全二叉树，一个数组就够了。 下标 i 的儿子是 2i / 2i+1，爸爸是 i/2 —— 不需要指针。 而它的高度数一数层数就证完了：2^(h+1) − 1 ≥ n ⇒ 树高 = ⌊log₂ n⌋（n = 2×10⁵ 时只有 17）。 ★ 上浮 / 下沉都只走一条根到叶的路，所以各是 O(log n) —— 这是最坏情况的界，不是均摊的。

【2】★★ 这一章的 log 和上一章的 α，是「能证」和「证不了」的一对。 第 36 章：α(n) 只给结论 + 三条实测曲线，明说「这一章不证」； 这一章：两条界都当场证完（数层数 / 一行级数），而且实测都被顶到了紧 （树高正好 ⌊log₂ n⌋、建堆的比较次数正好收敛到 2n）。

★ 能证的就证，证不了的就老实说证不了、然后拿实测顶上。

【3】★ 建堆自底向上只要 O(n)，因为「大多数点很矮」。 for (i = n/2; i >= 1; i--) down(i) —— 从 n/2 开始（一半的点没有儿子，白送）， 倒着走（「依赖谁，就先填谁」第八次登场）。 Σ h/2^h = 2 ⇒ 比较次数 ≤ 2n，实测递减数据上正好是 2.00 n。

【4】★★ 上界证出来了，不等于随机数据碰得到它。 push 的 O(log n)，随机数据上实测只花 2.28 次比较（而且几乎不随 n 变）， 只有递减插入才顶到 11.98 ≈ log₂n − 2。

第 33 章那条「要证明一个下界是紧的，就得自己造出那个最坏情况」的第二次现场。

【5】★★ 对拍看不见「慢」—— 这一章的现场比上一章还宽。 空穴法 vs 一路 swap（移动次数差 2.4 倍）、两种建堆方式（比较次数差 6 倍）、 甚至 linear / sorted 这两个完全不同的算法 —— 答案全都一模一样。 ★ 尺子只能是计数器（比较次数 / 移动次数）：次数可复现，秒数不可复现， 而秒表在正解身上已经快失灵了（20 万元素跑完全程 0.04 秒，其中 0.02 秒是读入）。

【6】★ 生成器：这一章又有两个直觉被实测打脸。

• 「顺手保证堆不为空」让「忘了判空」拿到 0 / 300（顺手写法第九次）；
• 照第 22 章的经验「把值域压小」，六列全线下降 —— 「值域小才是灵魂」不是普适规律；
• 「多删」单独加是全场最差（最弱支 25），配上「序列拉长」却把最弱支从 161 抬到 278 —— 调优不可加，第五次。

★ 而「题面多问一行」这件事，这一章给了一笔比第 36 章更接近常态的账： 弱数据上它值 5~11 倍，强数据上只值 283 → 290。两笔都要写。