题目与使用场景
Radix Heap 是为单调优先队列设计的整数结构，适合 Dijkstra 等按非降序取出键的算法。它利用最近弹出键作为边界，把元素放入按最高不同位划分的桶。
面试官考察什么
- 是否理解插入键必须不小于上次弹出键。
- 是否正确计算最高不同位和桶范围。
- 是否在最小非空桶重分布时更新基准。
- 是否保持桶内元素和最小键不变量。
- 是否处理空队列、整数溢出和违规回退键。
- 是否解释总重分布次数与摊销复杂度。
作答前的澄清问题
- 键是固定宽度无符号整数还是任意精度整数？
- 是否允许插入小于最近弹出键的元素？
- 需要稳定处理相同键的 payload 吗？
- 只支持
pop-min，还是还要 decrease-key 和删除？ - 空队列弹出和溢出应返回什么？
- 目标是代码清晰、低常数，还是严格的渐进复杂度？
30 秒回答框架
“我维护 last，表示最近弹出的键，并建立 W+1 个桶。键等于 last 放入桶 0；否则按 bit_length(key XOR last) 放入对应桶。弹出时若桶 0 为空，就从最小非空桶取最小键作为新 last，把该桶元素按新基准重新分桶，再从桶 0 弹出。违规的回退键直接拒绝。”
分步骤深入解答
步骤 1：建立不变量。 last 单调不减，所有待处理键都满足 key >= last；每个桶 i 的键与 last 的最高不同位为 i。
步骤 2：计算桶索引。 key == last 的索引为 0，否则使用 bit_length(key XOR last)；固定 W 位键需要 W+1 个桶。
步骤 3：实现插入。 检查非负、宽度和 key >= last，计算索引后把 (key, value) 放入桶；相同键可以共存。
步骤 4：实现弹出。 若桶 0 非空，任取其最小 payload；否则找到最小非空桶，扫描得到其中最小键并设为新 last。
步骤 5：重新分布。 清空该桶，把元素按新 last 重新计算索引；这些元素的索引会下降，且至少有一个进入桶 0。
步骤 6：处理边界。 空队列返回约定错误；超出固定宽度或小于 last 的键拒绝，避免异或和桶索引溢出。
步骤 7：说明复杂度。 每个元素跨桶重分布的次数受字长 W 限制；常见摊销为 O(W)，空间 O(n + W)，不应声称所有场景都优于二叉堆。
高质量示范回答
“我用 64 位无符号键和 65 个桶。last 初始为 0；插入键若小于 last 就报错，否则用 bit_length(key XOR last) 选择桶。pop 先取桶 0；桶 0 为空时，找到最低非空桶，扫描其最小键更新 last，再把桶中元素按新基准重分布。重复键保留各自 payload。空队列返回空值，溢出和回退键拒绝。每个元素最多经历与字长相关的重分布，空间为元素数加桶数。”
常见错误
- 允许键回退 → 桶不变量失效 → 拒绝
key < last。 - 用
log2(key)选桶 → 忽略当前基准 → 使用key XOR last。 - 重分布后不更新
last→ 可能错误弹出 → 先扫描最小键再分桶。 - 只取桶中第一个元素 → 不保证最小键 → 扫描并选择最小键。
- 宣称 O(1) 所有操作 → 忽略字长和重分布 → 说明
W与摊销条件。
追问及应对
追问 1：为什么适合 Dijkstra？
Dijkstra 的已取出距离单调不减，新的候选距离不会小于当前最小距离，满足 Radix Heap 的单调键前提。
追问 2：如果业务需要任意 decrease-key？
Radix Heap 不适合任意回退；改用二叉堆、配对堆或保留版本并惰性删除。
追问 3：桶 0 为什么可以直接弹出？
桶 0 中所有键都等于 last，因此它们都是当前最小键。
追问 4：如何证明重分布会下降索引？
新 last 是该桶的最小键；其他元素与它的最高不同位不会超过原桶索引，并至少有元素进入桶 0。
追问 5：相同键如何保持稳定顺序？
在 payload 中加入递增序号，桶 0 按 (key, sequence) 选择；若不要求稳定，可任意取出。
追问 6：负数键怎么办？
把键映射到无符号有序空间，或明确 API 只接受非负键；不能直接对带符号异或而不定义顺序。
追问 7：什么时候二叉堆更好？
键不是单调整数、字长很大、更新模式复杂或实现简单和通用性更重要时，二叉堆通常更合适。