任务进入队列后，优先级可能降低，两个队列也可能合并。只会插入和弹出最小值的堆接口还不足以描述这些操作：怎样定位旧任务、是否允许重复ID、合并后句柄是否仍有效，都会改变实现和成本。

本篇实现可定位元素的二叉最小堆，随后用二项树和势能法解释合并与降键的不同设计。Fibonacci堆采用结构推导，不把一个未实现的高级堆写成实测候选。令n为当前元素数，q为操作序列长度，比较键为 (priority,id)；ID唯一，相同优先级按较小ID先出队。

降键先要找到哪个元素

数组二叉堆只保存优先级时，要修改指定ID需要先扫描O(n)。为消除这次扫描，教学实现增加 pos[id]，记录该元素在数组中的下标。数组元素与位置映射必须互为逆映射；每次交换都同时更新两个位置。

操作 语义
insert(id,priority) 加入元素，重复ID抛ValueError
decrease(id,new) 只允许不增的优先级；缺失抛KeyError，增大抛ValueError
delete(id) 删除指定元素，返回(priority,id)；缺失抛KeyError
pop_min() 删除并返回最小(priority,id)；空堆抛IndexError

上浮时，除当前节点到根路径外，原堆序未变；只有当前节点可能小于父亲。与父亲交换后，冲突位置向上移动，原位置的子树重新满足堆序。下沉则在两个孩子中选较小者交换，保证另一个孩子也不小于新父亲。每步移动一层，树高为O(log(n+1))，因而终止。

降键只可能破坏父边，所以只需上浮。任意删除先用末尾元素填补空位，再根据与父亲的关系决定上浮或下沉；不能一律下沉。比如末尾元素来自另一分支，填到某个较大父亲下面时可能小于该父亲，这就要求上浮。删除末尾元素无需再访问已经缩短后的原下标。

堆比较和交换次数最坏O(log(n+1))，查看根为O(1)，逻辑空间O(n)。位置表采用Python字典，其查询不能无条件写为最坏常数；字典插入和数组增长还带有摊还成本。容器的实际总时间界须加上这些组件条件。逐个insert建堆最坏O(n log(n+1))次堆操作；线性heapify是另一个构造算法，本实现未提供。

重复入堆改变了什么

一种替代降键的方法是插入同一任务的新优先级，并在弹出时检查它是否仍是最新版本。它不需要找到旧位置，却允许堆中同时存在失效条目。此时n不再只是活跃任务数，空间与弹出总次数应按累计候选条目计算。忘记过滤旧条目会改变答案；完成过滤也不能把额外空间隐去。

可定位堆把成本用于维护位置不变量；重复入堆把成本推迟到弹出和清理。两者能服务相同上层需求，但底层状态和规模变量不同。后续最短路篇若使用重复入堆，必须按那个实现重新分析，不能套用本篇降键接口的计数。

合并为何需要另一种组织

把两个普通二叉堆数组拼接再heapify需要线性时间，不能像链表拼接一样直接得到合法堆。二项堆把元素组织成不同阶数的二项树。0阶树只有一个节点；两棵r阶树比较根，把较大根连接为较小根的孩子，就得到r+1阶树。

1
2
3
r阶根a       r阶根b             r+1阶根a
 /...         /...      ->        /... b
                                    /...

归纳可知r阶树有2^r个节点，根有r个孩子。规范二项堆每个阶数最多一棵树，其根列表对应n的二进制表示。合并时同阶树相连产生进位，涉及O(log(n1+n2+1))个阶数。单次插入也可能连续进位，不能把一连串连接的最坏代价写成常数。

Fibonacci堆放松“每阶只有一棵树”的即时要求，先把根放进根链表，直到删除最小根后才合并同阶树。合并两堆只拼接根链表并比较最小指针；它的常数成本以可常数拼接的双向链表和有效节点句柄为前提。若用Python列表复制两份根数组，就不是这个实现界。

为什么丢失第二个孩子要切断

标准Fibonacci堆的非根节点允许失去一个孩子，此时打标记；再次失去孩子就从父亲切断并放入根表，随后递归处理其父亲。第一次失去孩子不立即切断，降低了单次降键的修复工作；第二次切断则限制一个节点在仍作为孩子期间能缩水多少。

1
2
3
4
5
6
根r                    根表: r, x, p
 |                        |
 p*  (已失去过孩子)         其余子树保持
 |
 x   (降键后小于p)
切断x；p因第二次丢孩子也被切断并清除标记。

证明度数界时，将节点x的当前孩子按连接到x的时间排序为y₁…y_d。第i个孩子连接时，x已有至少i−1个更早且仍保留的孩子；同阶连接要求y_i当时度数至少i−1。y_i仍未被切走，所以此后最多失去一个孩子，当前度数至少i−2。以F₀=0、F₁=1定义Fibonacci数。度数0节点至少1个节点，度数1至少2个；更大的度数由第一个孩子至少一个节点及其余孩子的归纳界，得到子树至少有 2+Σ(i=2..d) F_i=F_(d+2) 个节点。由于Fibonacci数指数增长，最大度数D(n)=O(log(n+1))。

若允许一个非根节点无限次丢失孩子却不切断，上述“至多减少1”失效；当前度数不再约束孩子的大小，删除最小值时的对数度数分析便失去依据。标记的用途是维持这条历史不变量，不能仅当作一个优化开关。

用势能区分延迟与免费

令t为根数，m为被标记的非根节点数，取势能Φ=t+2m。具体实现的指针操作成本可以用常数倍势能配平；下面按根处理与切断等单位事件计数。

插入增加一个根，实际工作常数、势能只增1，因此摊还常数。合并把两堆的根数和标记数相加，势能相对两堆之和不增加；常数链表拼接得到摊还常数。

一次降键若触发k次切断，每切一个节点增加一个根。除最初可能未标记的节点外，后续被切节点原本已标记，切后清除标记；链尾最多新增一个标记。因此Δt=k，Δm≤2−k，得到ΔΦ≤4−k。切断的线性实际工作被势能下降抵消，降键摊还O(1)，而单次最坏仍可沿祖先链做许多切断。

删除最小根要把它的孩子转为根，并整理根表。同阶连接每次消去一个根，释放一个单位势能；处理现有大量根的成本由此前积累的根势能支付。整理结束后每个度数最多一个根，剩余根数与最小根度数都受D(n)控制，所以删除最小值摊还O(log(n+1))。这是序列分析，不承诺当前根表很长时单次删除仍对数。

检验实现而不是名称

运行 python3 examples/advanced-algorithms/check_indexed_heap.py。本次16105条长度至多4的穷举序列共62810步、496个逐位置删除用例、14步边界检查、seed20260919的20000步随机混合操作均通过；原始stdout在 examples/advanced-algorithms/results/indexed_heap.json。配套接口检查卡说明异常语义。本篇程序只验证可定位二叉堆；二项堆合并和Fibonacci堆分析由结构归纳与势能证明承担，不标记为运行实验。检查应以独立字典的min结果作为参照，每步审计堆序与双向位置关系，并覆盖相同优先级、删除末尾和不合法降键。

练习

  1. 构造一个合法二叉堆，删除非根元素后，末尾补位元素必须上浮。写出数组及位置表，说明只下沉会留下哪条违反堆序的边。
  2. 对连续插入后一次pop_min的Fibonacci堆，分别估计单次实际根处理数与整段摊还成本。再说明重复入堆方案中的n应如何定义，才能公平地与可定位堆比较空间。

参考资料