d 叉堆是什么？它和二叉堆相比有什么取舍？
简化版
d 叉堆就是每个节点最多有 d 个孩子的堆。
二叉堆是 d = 2 的特例。d 叉堆的高度更低，所以插入上浮路径更短；但下沉时要在最多 d 个孩子里找最优孩子，单层比较次数更多。
因此 d 叉堆适合插入和 decrease-key 多、删除堆顶相对少的场景。很多图算法或调度系统会根据读写比例选择合适的 d。
详细版
二叉堆中，节点 i 的孩子下标通常是 2i + 1 和 2i + 2。
d 叉堆把这个关系推广成：
children(i): d*i + 1 ... d*i + d
parent(i): (i - 1) / d当 d 增大时，堆的高度大约从 log2 n 变成 logd n。这会减少上浮和下沉经过的层数。
但删除堆顶时，每下降一层都要从 d 个孩子中选出最小或最大者，所以单层比较成本变高。
| 操作 | 二叉堆 | d 叉堆 |
|---|---|---|
| 插入 | O(log2 n) | O(logd n) |
| 删除堆顶 | 每层比较少 | 层数少但每层比较多 |
| 空间 | 数组 | 数组 |
面试回答重点不是说 d 越大越好，而是说它在高度和单层比较之间做权衡。
完整版教学
1. 从二叉堆自然推广到 d 叉堆
二叉堆之所以常见，是因为实现简单、常数稳定。
但堆的核心要求并不是「必须两个孩子」，而是：
- 结构上接近完全树；
- 顺序上满足父节点优先级不低于或不高于子节点；
- 可以用数组紧凑存储。
d 叉堆只是把每个节点的孩子数从 2 扩展到 d。
d 叉堆本质上仍然是数组堆，只是父子下标公式变了。
2. 数组下标公式怎么推
如果数组从 0 开始，节点 i 的第 k 个孩子是：
child(i, k) = d * i + k
其中 k = 1, 2, ..., d父节点是：
parent(i) = floor((i - 1) / d)比如 d = 4 时：
| 节点 i | 孩子范围 | 父节点 |
|---|---|---|
| 0 | 1,2,3,4 | 无 |
| 1 | 5,6,7,8 | 0 |
| 2 | 9,10,11,12 | 0 |
这说明 d 叉堆依然不需要指针，空间局部性很好。
3. 高度为什么会降低
二叉堆每一层最多容纳 2^level 个节点，而 d 叉堆每一层最多容纳 d^level 个节点。
所以容纳 n 个元素时，高度大约是：
height = O(log_d n)例如 n = 1,000,000：
- 二叉堆高度约
20； - 四叉堆高度约
10； - 八叉堆高度约
7。
高度降低意味着上浮路径更短，这对大量插入或降低优先级的场景很有吸引力。
4. 为什么删除堆顶不一定更快
删除堆顶需要把最后一个元素放到根，再一路下沉。
二叉堆每层只要比较两个孩子，选一个更优的孩子交换。
d 叉堆每层要在最多 d 个孩子里找最优者：
best = firstChild
for each child in children:
if child better than best:
best = child因此 d 增大后：
- 层数减少；
- 每层比较次数增加。
这就是典型的常数权衡，而不是单纯的大 O 结论。
5. decrease-key 场景为什么常提 d 叉堆
在一些图算法里，可能会频繁发生 decrease-key。
decrease-key 通常是让某个节点优先级变高，然后上浮。上浮每层只需要和父节点比较一次，所以 d 叉堆高度越低，上浮越快。
如果工作负载是：
| 操作 | 次数特点 |
|---|---|
| 插入 | 多 |
| decrease-key | 多 |
| 删除堆顶 | 相对少 |
那么 d 叉堆可能比二叉堆更合适。
6. d 应该取多大
没有一个永远最优的 d。
实际选择要看：
- 元素规模；
- 插入、更新、删除堆顶的比例；
- CPU 缓存和分支预测；
- 比较函数是否昂贵；
- 语言运行时和标准库实现。
工程里常见的是 4 叉堆，因为它在高度和单层比较之间比较平衡，也比较适合缓存局部性。
7. 和二叉堆的面试对比话术
可以这样回答：
| 维度 | 二叉堆 | d 叉堆 |
|---|---|---|
| 孩子数量 | 2 | d |
| 高度 | 较高 | 较低 |
| 上浮 | 层数更多 | 层数更少 |
| 下沉 | 每层比较少 | 每层比较多 |
| 实现复杂度 | 最简单 | 稍复杂 |
| 适合场景 | 通用 | 更新多、插入多的场景 |
这类题的关键是体现取舍意识：d 叉堆不是淘汰二叉堆，而是在特定负载下优化常数。
8. 常见误区与追问
- 误区：d 叉堆的复杂度一定比二叉堆好。 大 O 仍然是对数级，真正变化的是高度和比较次数的常数。
- 误区：d 越大越好。 d 太大会导致每次下沉扫描太多孩子，删除堆顶可能变慢。
- 误区：d 叉堆不能用数组存储。 它和二叉堆一样可以用数组，只是下标公式不同。
- 追问：为什么四叉堆比较常见？ 因为高度明显下降，同时每层比较成本还可控，是比较折中的选择。
- 追问：d 叉堆适合什么业务？ 适合任务优先级频繁变化、插入多、需要较好缓存局部性的优先队列场景。