基数堆（Radix Heap）的原理与操作 1. 问题背景与定义 基数堆 是一种基于数字位数（基数）进行分桶的优先级队列，适用于键值为整数的场景，尤其在最短路径算法（如Dijkstra算法）的优化中具有理论价值。它的核心思想是：将数字键值按其二进制表示的比特位划分为多个桶，利用整数比较的特性减少键值调整（降低优先级）的操作开销。 特点 ： 键值必须为非负整数。 插入、删除最小元素的时间复杂度可达到 O(log C) （C为键值范围），键值减少操作可在 O(1) 分摊时间内完成。 常用于键值范围较小或变化规律性强的场景，如稠密图中的最短路径计算。 2. 基数堆的结构设计 假设键值范围为 [ 0, C] ，用二进制表示的最大位数为 K = ⌈log₂(C+1)⌉ 。 设置 K+1 个桶（bucket），编号 B₀, B₁, …, Bₖ 。 每个桶存储键值在特定二进制范围下的元素。 桶的划分规则 （以二进制表示分析）： 令 msb(x) 表示 x 的最高有效位（most significant bit）位置（从0开始计数，最低位为0）。 桶 B₀ 存放键值 x 满足 msb(x) = 0 的元素（即 x = 0 ）。 对于 i ≥ 1 ，桶 Bᵢ 存放键值 x 满足 msb(x) = i 的元素，这意味着： \[ 2^{i-1} ≤ x < 2^i \] 但注意，实际操作中我们采用 动态范围划分 ，依赖一个全局变量 last_ min 记录已提取的最小键值，桶的边界是动态计算的。 3. 操作步骤详解 步骤1：插入操作（insert） 给定键值 x ，根据其与 last_ min 的差值确定桶编号： 计算 d = x - last_ min ，若 d ≤ 0 ，直接将 x 放入 B₀ （因为键值必须非负且不小于当前最小）。 否则，找到 msb(d) 的位置 i ，将元素放入桶 Bᵢ 。 时间复杂度：计算 msb(d) 可用位运算在 O(1) 完成。 步骤2：提取最小元素（extract_ min） 找到第一个非空的桶 Bᵢ ，如果 i = 0 ，则从 B₀ 中弹出最小元素（因为桶内元素键值都等于 last_ min ）。 如果 i > 0 ，则需要“重分布”桶 Bᵢ 中的所有元素： 在 Bᵢ 中找到当前最小键值 min_ val 。 更新 last_ min = min_ val 。 对 Bᵢ 中每个其他元素 y ，计算新的差值 d' = y - last_ min ，根据其 msb(d') 分配到更小的桶中（可能是 B₀, B₁, …, B_ {i-1} ）。 重分布确保元素总是从高编号桶向小编号桶移动，避免重复扫描。 均摊复杂度：每个元素最多被重分布 O(log C) 次，因此 extract_ min 的均摊时间为 O(log C) 。 步骤3：键值减少（decrease_ key） 基数堆的一个关键优势是支持快速键值减少。 当某个元素的键值从 x 减少到 x' 时，直接将其从原桶中删除，然后以新键值 x' 重新插入（即按 x' - last_ min 放入对应桶）。 由于键值减少后差值 d 的 msb 不会增加，元素可能移到编号更小的桶，但不会移到更大编号的桶，这保证了重分布的一致性。 时间复杂度： O(1) 均摊（因删除和插入均为常数操作）。 4. 实例演示 假设键值范围 0~15（K=4），初始 last_ min=0 ，桶 B₀~B₄ 初始为空。 插入键值 5： d=5-0=5 (二进制101)， msb(d)=2 ，放入 B₂ 。 插入键值 3： d=3 ， msb(d)=1 ，放入 B₁ 。 插入键值 8： d=8 ， msb(d)=3 ，放入 B₃ 。 提取最小元素 ： 第一个非空桶是 B₁ （含键值3），执行重分布： 找到 min_ val=3 ，更新 last_ min=3 。 桶中只有元素3，无其他元素，结束。 此时 B₀ 仍为空， B₂ 中有元素5： d=5-3=2 ， msb(d)=1 ，应移动到 B₁ 。 之后提取时，从 B₁ 取出元素5，继续类似过程。 5. 复杂度分析 空间： O(n + K) ，n为元素个数。 时间： 插入： O(1) 。 键值减少： O(1) 均摊。 提取最小： O(K) 最坏，但均摊 O(log C) （K与log C同阶）。 6. 应用场景 经典应用： Dijkstra算法 中，当边权为非负整数且范围有限时，使用基数堆可优化键值更新，得到 O(m + n log C) 的时间复杂度，优于二叉堆的 O(m log n) 。 适合键值范围小、键值减少频繁的场景。 关键理解 ：基数堆通过二进制分桶，将比较操作转化为“最高有效位”计算，并利用差值动态调整桶边界，使键值减少操作极为高效。这是 优先级队列在整数域上的特化优化 ，体现了数据结构设计与问题特性结合的巧妙思路。