比较排序需要从比较结果中区分输入排列，因此有最坏Ω(n log n)比较次数下界。整数键还允许取位、移位和按数值寻址。利用这些操作的算法改变了模型，不能用“击败下界”来描述，也不能忽略键域和机器字长的代价。

本篇用小整数宇宙位向量实现严格前驱，再用稳定基数排序说明按位处理的成本。经典van Emde Boas结构用于解释递归缩小键域的理论方法，与16篇的静态树地址布局是不同对象。

键放进一字，不等于宇宙放进一字

设宇宙为整数集合[0,U)，当前集合有n个不同键，机器字长w位。键可以放入一字通常要求U≤2^w；若用一位表示一个宇宙元素，整个位向量放入一字却需要U≤w。两个条件相差很大。

word-RAM按字存取，指定的算术、位运算与索引按常数成本计算。若用最高置位位置直接得到前驱，还要明确提供常数时间MSB或bit-scan原语，不能只看到代码有一个函数调用就当成常数时间指令。

严格前驱定义为集合中小于x的最大键，不存在则返回空值。它不同于“小于等于x”的前驱约定。教学接口允许查询x=U以取得全体最大键；插入、删除和成员检查仍只允许0≤x<U。

一个位向量怎样实现严格前驱

令整数bits的第i位表示键i是否存在。插入设置该位，删除清除该位；重复插入和删除不存在键返回未改变。查询x时，只保留低x位：

low=bits  &  (2x−1).low=bits\;\&\;(2^x-1).

若low为0，没有严格小于x的键；否则最高置位下标就是答案。在Python里可写low.bit_length()-1。x=0时掩码为0，x=U时保留全部合法键，边界与严格前驱定义一致。

正确性来自位与集合成员的一一对应。掩码恰好保留下标小于x的位，最高留下的位对应其中最大元素。无须假设插入顺序，也没有随机失败概率。

当U≤w且具有常数时间最高置位原语，这些操作在单字模型中最坏O(1)，位存储为U位。若U跨多个字，扫描或位运算必须计入字数；不能继续沿用单字界。Python官方文档定义int为无限精度整数，因此本实现只是这种集合表示的教学版本。按常见分字实现做保守计费，处理U位掩码可能涉及O(⌈U/w⌉)个字，临时大整数也可能占相应空间；这里不是Python文档承诺的版本耗时，也没有测量具体解释器的速度。

若只存一个很大的键U−1，位向量仍可能需要与U成比例的位空间，而不是与n成比例。稀疏集合不能只看当前元素数来判断这项表示是否节省内存。

LSD基数排序依赖稳定性

对非负整数，每轮取b个位作为一个数位，基数R=2^b，从低位向高位分桶。每个桶按输入到达顺序保留元素，再按桶号递增连接。这样一轮是稳定的：同一数位的元素保持此前顺序。

归纳证明是：完成第t轮后，元素按最低tb个位排序。下一轮先由新数位分组，相同新数位内保留原顺序，于是同时按更低位有序，得到最低(t+1)b个位有序。处理完所有有效位即得到整数顺序。

例如十进制输入[12,11]按个位排序得到[11,12]。十位相同，如果这一轮不稳定而反转桶内顺序，就会返回错误的[12,11]。稳定性是正确性条件，不只是让相同键看起来顺序更自然。

设最大键需要ℓ位，d=ceil(ℓ/b)。单位成本取位模型下，每轮建立R个桶并扫描n个键，轮次时间O(d(n+R))，连同复制输入与确定最大位长，总时间O(n+d(n+R))，额外空间O(n+R)。教学版本将b限制在1到8以避免无意申请巨量桶，空输入直接返回；所有键为0时不需要数位轮次。负数被拒绝，不能把无符号取位规则直接推广成带符号整数排序。

若ℓ远大于机器字长，取位和移动大整数也有成本，O(n+d(n+R))只是在指定单字操作模型下的计数。与比较排序的关系取决于键宽与n的比例，并非整数输入一律线性。

van Emde Boas把递归规模换成字长

经典结构使用U=2^k的宇宙，把键拆成高位簇编号和低位簇内位置。高位占ceil(k/2)位，低位占floor(k/2)位；summary记录非空簇编号，clusters保存各簇内部的同类结构，另外直接保存集合的min和max。k很小时用常数大小基例。

关键安排是min不再递归存入cluster。插入非空簇只需深入这个簇；插入空簇时，建立簇内单元素状态是常数操作，非平凡递归用于更新summary。查询严格前驱时，先处理空集、x≤min时无答案，以及x>max时直接返回max。其余情况下，若当前簇里有比低位更小的元素，就在该簇递归；否则递归到summary找前一个非空簇，再直接读该簇max。若summary中也没有前簇，答案仍是全局min，因为它没有存入簇且此时min<x。例：U=16、集合{1,4}、查询x=3，前驱是1，不能因簇中找不到候选就返回空。两条非平凡递归情况互斥，不是每次都递归两个子结构。

删除类似：若删掉min，从首个非空簇提取新min；一个簇变空时，对该簇的最后元素处理为常数工作，递归成本落在summary。重复插入或删除不存在元素须先用成员检查处理，或把合法操作写成前提，不能破坏summary与簇非空性的对应关系。

于是一次操作的非平凡递归满足字长递推T(k)≤T(ceil(k/2))+O(1)，得到最坏O(log k)，即O(log log U)，小宇宙按常数基例处理。这是经典结构的确定性最坏界，不是哈希表意义的期望界。

代价是完整预分配结构占O(U)个字，逐节点初始化也需O(U)时间。它比位向量的U位空间还多，不能把两者的“线性于U”混为同一存储量。U极大而n很小时，预分配可能根本不可行。

压缩变体不能只换掉一个容器

只为非空簇建立对象可以减少实际分配，但由此不能直接宣布获得O(n)空间与经典最坏操作界。对象存在多少层、summary怎样维护、字典使用什么哈希假设、更新是否摊还，都需要重新分析。

MIT讲义讨论的哈希压缩方案，以及其他整数前驱结构，带有各自的空间与概率条件。把“哈希期望常数查找”“经典vEB最坏O(log log U)”和“某种压缩结构线性空间”拼在一起，不是一个已经证明的实现。本篇没有实现这些变体；小宇宙位向量、稳定基数排序和经典vEB理论分别标明成本。

可复跑教学检查

实现位于examples/advanced-algorithms/integer_universe.py。BitUniverse(U)要求正整数宇宙，add和discard返回是否改变成员关系，contains返回布尔值，predecessor不存在时返回None。radix_sort(values,digit_bits=4)返回新列表，不改输入。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_integer_universe.py

独立参照使用Python集合与排序，实际枚举U=1到8的全部510个子集，通过7682次成员及前驱查询、17930次增删调用；U=256另检查跨字边界。基数排序枚举1365个短数组，在四种数位宽度下完成5460次排序对照；种子20260920的100组随机检查使用257位非负整数，另检查16种拒绝路径。真实结果位于examples/advanced-algorithms/results/integer_universe.json。

这些计数来自已运行的教学检查，不是时间或内存跑分。257位输入只说明实现可正确处理这些有限用例，没有证明无限精度移位是常数时间。经典vEB、压缩vEB和硬件bit-scan均未实现或测量。

练习

  1. w=64、U=2^32、n=100时，一个键与整个位向量分别需要多少位？解释为什么“键可放一字”不能证明前驱查询的单字O(1)界。
  2. 集合为{1,4,7}，写出查询x=0、4、8的严格前驱。再解释经典vEB查询为什么只产生一条非平凡递归链；若无条件搜索当前簇和summary，会把哪条递推式写错？

参考资料