单调整数键的 Radix Heap

桶队列遇到距离一百万时，可能为了越过大片空距离而走一百万步。Radix heap不为每个整数开一个槽，而是把远离当前最小值的键先装进宽桶；直到这个桶真的成为最小候选，再展开其中的细节。它能这样延迟排序，依靠的是新插入键不会退到已弹出最小值的左边。

形式陈述

单调承诺与本页接口

本页给出一种最小优先队列的专用表示，键为 $[0,U]$ 内整数，U在初始化时给定。维护 last，初始为零，每次弹出后令它等于所弹出的键；每次插入必须满足

\text{last}\le\text{key}\le U.

这是相对于最后弹出值的承诺，不是要求按时间先后插入的键也非降。last=4时，先插入九、再插入五完全合法；插入三则违反接口。允许重复键，不保证相同键的先进先出。

实现暴露 push(key,item) 和 pop()；空弹出抛出错误。它没有给任意记录的减键、删除或合并接口，也不承诺高效peek。尤其不能把“先重分配并推进last”的内部准备过程随意当peek：若还没有弹出，就可能无意禁止本来允许插入的较小键。

最高差异位决定桶号

令 $W=\lceil\log_2(U+1)\rceil$ ，等价于U的二进制位数；U=0时W=0。使用桶 $B[0],\ldots,B[W]$ ，定义

b(x)=\operatorname{bitlength}(x\mathbin{\mathrm{xor}}\text{last}), \qquad\operatorname{bitlength}(0)=0.

B[0]恰装着等于last的键。对i>0，B[i]中的键和last在第i−1位首次出现从高到低的差异；更高位相同。由于x≥last，差异位必是last为零、x为一。

下列代码独立给出通用定界键版本。Python bit_length() 对应最高置位查询；复杂度的机器字假设在后文单独说明。

python

class RadixHeap:
    def __init__(self, upper):
        if type(upper) is not int or upper < 0:
            raise ValueError('bad key upper bound')
        self.upper = upper
        self.last = 0
        self.size = 0
        self.buckets = [[] for _ in range(upper.bit_length() + 1)]

    def push(self, key, item):
        if type(key) is not int or not self.last <= key <= self.upper:
            raise ValueError('monotone key contract')
        index = (key ^ self.last).bit_length()
        self.buckets[index].append((key, item))
        self.size += 1

    def pop(self):
        if not self.size:
            raise IndexError('empty radix heap')
        if not self.buckets[0]:
            index = 1
            while not self.buckets[index]:
                index += 1
            self.last = min(key for key, _ in self.buckets[index])
            items = self.buckets[index]
            self.buckets[index] = []
            for key, item in items:
                new_index = (key ^ self.last).bit_length()
                self.buckets[new_index].append((key, item))
        self.size -= 1
        return self.buckets[0].pop()

直觉

为什么只看最小非空桶

若B[0]非空，它们已经等于last，而所有键都不小于last，直接弹出即可。否则找到最小非空桶B[i]。任何更高桶B[j]，j>i，其键在更高的第j−1位已经比last大；B[i]的键在那一位还与last相同。因此B[i]的每个键都小于更高桶的每个键，全局最小值一定藏在B[i]里。

同一个桶内仍可能含多个不同键，不可以随便弹出一个。代码先扫描B[i]找到真正最小值M，将last改成M，再按新基准重新分桶。至少一个元素的键等于M，因而B[0]非空，最后一步确实能返回全局最小值。

重分配为什么严格向下

选中桶B[i]的全部键，在旧last的最高差异位i−1上都是一，在更高位完全相同。新最小值M也是其中一个键，所以任意两个旧B[i]键之间都不可能在i−1或更高位不同。于是它们与M的异或位数严格小于i，每个被搬动的记录都进入编号更小的桶。

更高桶则不用动。j>i时，旧last与M在第j−1位及更高位相同；原B[j]键的最高差异仍在j−1。较低桶本来为空。这样只重排一个桶就恢复全局不变量，不必重新散布队列里所有记录。

基准二时桶三含四和六，最小值改成四后它们进入更低桶；键八仍留在更高桶 — 最高差异位消失，选中桶中的每个记录严格降桶

例子与边界

从基准二走到基准四

设last=2，即二进制0010，记录键为4、6、4、8。前面三个键与2的异或分别为0110、0100、0110，位数均为三，放在B[3]；8 xor 2=1010，位数四，放B[4]。

B[0]至B[2]为空，所以选中B[3]，扫描得到M=4。更新last后，两份4都进入B[0]；6 xor 4=0010，进入B[2]。8 xor 4=1100仍是四位，原B[4]不用动。弹出一个4，下一次还可直接弹出另一个4；不是“每次pop都会推进last”。

此时插入五合法，插入三须拒绝。若错误接受三，它的最高差异位相对于四虽然可计算，却已不再保证该位是键一、last零；前面“低编号桶必含更小键”的证明随之失效。单调承诺是正确性条件，不只是速度建议。

空范围、重复键和整数表示

U=0时只有B[0]，可以保存任意多份键零，直到依次弹空。键的身份与数值分开：两份键四可能分别代表不同任务，也可能代表一个顶点的旧、新记录，是否过时由调用方判断。

本页以非负整数的无符号位表示为准。负数在不同语言中的移位、异或与位长含义不同，不能把它们直接塞进同一公式。浮点数也不能先截成整数再使用：截断可能改变优先次序；按浮点位模式排序需要另外证明编码和符号处理。

推论与应用

把代价计到每份记录的下降次数

在Word-RAM模型中，假设U和地址都装入机器字，异或与最高置位查询均为常数成本。桶数组初始化为O(W+1)；列表尾插若偶尔扩容，按摊还常数成本计算。单次pop可能扫描并搬动一整个桶，最坏可达当前记录数加W，不能称逐次最坏O(W)。

用摊还分析看完整操作序列。每份记录初始桶号至多W，每次被重分配时至少下降一，从不因别的桶重基准而升高，所以每份记录最多搬W次。查找最小值的扫描和重分配扫描，都可逐项收费到这些下降上。

寻找最小非空桶时还要跨过i个桶号。这项开销也不能漏掉：本轮至少有一份最小键记录从i直接降到零，可以用它减少的i单位桶号支付。设共插入M份记录、弹出X次，则包括初始化的总时间为

O\bigl((M+1)(W+1)+X\bigr),

空间为当前记录数加W+1。这个界把尚未弹出的记录也算在内，不依赖“最后一定清空队列”。若处理任意长Python整数，应另计异或、比较和位长的实际多字成本；代码能运行不等于这些运算无条件是一条机器指令。

作为Dijkstra的惰性队列

Dijkstra有效弹出距离d后，新插入键为d+w，非负权保证它不小于d。跳过旧项时没有新插入；因此包括旧快照在内的整列弹出键也非降，满足radix heap的接口。

对于n点、最大整数边权C的图，可保守设置U=nC，所有生成的有限候选都不超过这个值。惰性版本总共至多m+1次插入，取W为nC的位数，得到

O\bigl(n+(m+1)(1+\log(nC+1))\bigr)

的保守时间界，辅助空间 $O(n+m+\log(nC+1))$ 。它跳过了Dial逐个扫描的空距离，但不能由此宣布对任何图都更快。

原始radix-heap最短路文献还有更精细的 $O(m+n\log(C+1)+n)$ 界。[1][2] 那个版本利用当前键窗口宽C，将高桶截顶，并使用带句柄的常数时间减键；每个顶点只支付一次初始桶预算。本页的通用U定界、惰性重复插入代码没有实现这些额外条件，所以不套用它们的时间界。

在本单元整数图上，重基准从二到四时恰出现图中的搬桶；到t的距离仍是四，路径仍为 $s\to b\to a\to c\to t$ 。队列表示改变的是操作成本，不能改变路径问题或把旧a的费用四重新当成一次有效结算。

参考资料

[1] Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin and Robert E. Tarjan, “Faster Algorithms for the Shortest Path Problem”, Journal of the ACM 37(2), 1990, pp.213–223，DOI：radix heaps及利用整数边权范围的专用最短路界。
[2] Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger and Roman Dementiev, Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox, Ch.10, 2019，§10.5.2，pp314–316，特别是Lemma10.8：最高差异位与严格降桶。教材同时证明有限窗口的截顶桶版本；本文先给不截顶的通用实现。

形式陈述 ​

单调承诺与本页接口 ​

最高差异位决定桶号 ​

为什么只看最小非空桶 ​

重分配为什么严格向下 ​

从基准二走到基准四 ​

空范围、重复键和整数表示 ​

把代价计到每份记录的下降次数 ​

作为Dijkstra的惰性队列 ​

反向链接