題目與使用場景
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 非空時直接取；否則找到最小非空桶，掃描得到其中最小鍵並設為新 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：什麼時候二元堆更好？
鍵非單調整數、字長很大、更新模式複雜，或實作簡單與通用性更重要時，二元堆通常更合適。