d-ary heap · 树高 · cache line

d 叉堆：分支数怎么选

二叉堆的父子关系是下标算术：parent(i) = (i-1)/2、child(i,k) = 2i+k+1。把式子里的 2 换成任意的 $d$ ，整套结构原样成立，只是每个节点从两个孩子变成 $d$ 个。

改这一个参数会同时动到三件事，本页依次是它们：树高变成 $\log_d n$ 、每层的比较次数变成 $d$ 、一个节点的全部孩子在数组里连续排列的长度变成 $d$ 。前两件互相拉扯，第三件与前两件无关——本页的结论就落在这个错位上。

1 · 同一套下标算术

图 1-1 · d 从 2 到 8 的堆，上方按层展开，下方是底层数组。橙色是本次 push 或 pop 走过的路径。可拖动 d 观察树高变化，逐个 push 或 pop 看路径长短。

两个基本动作的代价并不对称，这是全页的关键：

push（上浮）：每层只与父亲比一次，共 $\log_d n$ 层，比较次数 $\log_d n$ 。 $d$ 越大越便宜。
pop（下沉）：每层先在 $d$ 个孩子里挑出最小的（ $d-1$ 次比较），再与父亲比一次，共 $d$ 次；层数 $\log_d n$ ，比较次数 $d \log_d n$ 。 $d$ 越大越贵。

真实负载里 pop 通常比 push 多做功——堆排序与 Dijkstra 都是「装一遍、弹一遍」，而 pop 每次要走满全高，push 平均只走两三层（新元素多半就落在底层附近）。所以总代价基本由 pop 那一项主导。

2 · 比较次数在 d = 3 取最小

把 pop 的比较次数展开：

$\displaystyle d \log_d n = d \cdot \frac{\ln n}{\ln d} = \frac{d}{\ln d} \cdot \ln n$

$\ln n$ 是常数因子，形状全在 $d / \ln d$ 上。这个函数求导得零点在 $d = e \approx 2.718$ ，整数里最近的是 3。

图 2-1 · 九个 d 值在四个指标下的对照，柱状图是当前选中的指标。表格最后一栏是 d / ln d。可换元素个数与指标。

4000 个 key 装入再全部弹出的实测：

$d$	树高	push 比较	pop 比较	总比较	移动	$d/\ln d$
2	11	9098	75931	85029	92991	2.885
3	8	6921	74918	81839	62961	2.731
4	6	6247	81226	87473	52441	2.885
8	4	5207	112801	118008	38295	3.847
16	3	4689	174734	179423	31083	5.771
32	3	4424	299344	303768	27589	9.233

pop 那一栏与 $d/\ln d$ 的形状严丝合缝： $d = 2$ 与 $d = 4$ 的理论值都是 2.885，实测 75931 与 81226 也确实相近； $d = 3$ 是唯一低于它们的点。 $d = 32$ 时理论值涨到 9.233，实测比较次数是 $d = 3$ 的四倍。

这条曲线有一处容易被记反：二叉堆并不是比较次数最少的。 $d = 2$ 输给 $d = 3$ ，只是差得不多（85029 对 81839，约 4%）。教科书默认取 2，理由是下标算术能用移位而非除法，不是因为它比较次数最优。

3 · 移动次数一路降到底

同一张表的最后两栏讲的是另一件事。移动次数只与树高有关——上浮或下沉走几层就搬几次——所以它随 $d$ 单调下降，从 $d = 2$ 的 92991 一路降到 $d = 32$ 的 27589，降了 70%。

两个指标的最优点差了一个数量级：比较次数最优在 3，移动次数最优在 32（以及更大）。选哪个取决于比较与移动谁更贵。key 是整数时比较几乎免费、移动也便宜，两者同阶；key 是长字符串或大结构体时移动远贵于比较， $d$ 就该往大了取。

4 · 真正决定 d 的是 cache line

现实中的实现（Boost 的 d_ary_heap、若干 Dijkstra 实现、Go runtime 早期的定时器堆）取的是 4 或 8，既不是 3 也不是 32。理由不在上面两张表里。

一个节点的 $d$ 个孩子在数组里是连续的：下标 $di+1$ 到 $di+d$ 。下沉时要读遍这 $d$ 个孩子，若它们落在同一条 cache line 上，这一层只付一次访存；落在两条上就付两次。64 字节的 cache line 装得下 8 个 4 字节整数或 8 个 8 字节指针—— $d = 8$ 正好一条线。

于是账要这么算： $d = 2$ 时每层付一次访存、树高 $\log_2 n$ ； $d = 8$ 时每层也付一次访存（同一条线）、树高只有 $\log_8 n = \log_2 n / 3$ 。访存次数直接降到三分之一，而多出来的那几次比较发生在已经进了 L1 的数据上，几乎不要钱。上面那张表把每次比较都记作等价代价，这个假设在现代 CPU 上不成立——它算的是指令账，真正贵的是访存账。

这也解释了 $d = 32$ 为什么反而不好：32 个孩子跨四条 cache line，每层四次访存，树高只比 $d = 8$ 少一点，得不偿失。

5 · 参考文献

Johnson, D. B. (1975). Priority queues with update and finding minimum spanning trees. Information Processing Letters, 4(3), 53–57.
Naor, D., Martel, C. U., & Matloff, N. S. (1991). Performance of priority queue structures in a distributed environment. Concurrency: Practice and Experience, 3(1), 1–24.
LaMarca, A., & Ladner, R. E. (1996). The influence of caches on the performance of heaps. ACM Journal of Experimental Algorithmics, 1, 4.