二项式堆Binomial Heap— 支持高效合并的森林型优先队列077二项堆一个用二进制计数的数据结构5W1H 发明者故事Who何人- 发明者是谁发明者Jean Vuillemin让·维耶曼背景Jean Vuillemin 是法国著名计算机科学家INRIA法国国家信息与自动化研究所研究员他在算法理论和数据结构领域做出了多项基础性贡献他还是 VLSI 计算复杂性领域的重要学者曾在 MIT 和斯坦福访问研究1978 年他在 Communications of the ACM 发表论文A data structure for manipulating priority queues正式提出二项式队列When何时- 什么时候发明的时间1978年论文发表于 Communications of the ACMCACM时代背景1970 年代末是优先队列理论研究的活跃时期左倾堆Crane, 1972已能实现 O(log N) 合并但实现较复杂研究者希望找到概念更清晰、操作更规整的合并型优先队列同一时期Tarjan 和 Sleator 正在研究摊销分析方法Where何地- 在哪里发明的地点法国INRIAInstitut National de Recherche en Informatique et en Automatique环境INRIA 是欧洲最重要的计算机科学研究机构之一法国学者在算法和数据结构理论上有深厚积累与苏联和美国并列为三大重镇1970 年代欧洲计算机科学研究获得政府大力支持What何事- 发明了什么数据结构二项式队列Binomial Queue/ 二项式堆Binomial Heap核心组成二项式树Binomial Tree的有序森林二项式树 Bk 的递归定义B₀单个节点Bk将一棵 Bk-1 作为另一棵 Bk-1 的根的最左子树B0 B1 B2 B3 o o o o | /\ /|\ o o o o o o | |\ | o o o o | o二项式堆的结构由若干不同阶的二项式树组成的森林每种阶至多一棵N 个节点的堆恰好使用 N 的二进制表示中为 1 的各阶树例如N131101₂则包含 B3、B2、B0Why何因- 为什么发明要解决的问题需要一种比左倾堆更系统、更易于分析的合并型优先队列基于二进制计数的类比使得操作的正确性更直观支持 decrease_key 操作用于 Dijkstra 等图算法理论依据Bk 恰好有 2^k 个节点高度为 kN 个节点的二项式堆最多有 ⌊log₂N⌋1 棵树合并类比于二进制加法同阶树合并进位O(log N) 步完成插入是将单节点堆B₀与原堆合并当时的挑战证明二项式树的结构性质节点数、高度、各层节点数设计高效的链表表示使合并操作真正达到 O(log N)正确实现 extract_min 后的堆重建How何果- 如何实现有什么影响合并算法类比二进制加法将两个堆按树的阶从小到大对齐 逐阶处理类似二进制加法的进位 - 若某阶只有一棵树直接放入结果 - 若某阶有两棵树合并较大根成为另一树的子树产生进位到下一阶 - 若某阶有三棵树进位两堆各一棵其中一棵直接放入结果另两棵合并进位各操作时间复杂度操作最坏时间摊销时间insertO(log N)O(1)find_minO(log N)O(log N)extract_minO(log N)O(log N)mergeO(log N)O(log N)decrease_keyO(log N)O(log N)历史影响直接启发了斐波那契堆Fredman Tarjan, 1984斐波那契堆将 insert 和 decrease_key 的摊销代价降至 O(1)二项式堆至今是教科书中讲授摊销分析的标准例子CLRS 第 19 章在实践中由于常数因子小且实现简单二项式堆有时优于斐波那契堆今天的使用Dijkstra 最短路径算法的实现decrease_key 操作Prim 最小生成树算法作业调度系统中的优先级队列C STL 的一些优先队列变体自然语言需求定义需求名称实现二项式堆支持插入、查找最小、删除最小、合并两堆、减小 key 值功能需求用精确的中文描述合并/联合merge/union将两个二项式堆合并为一个输入两个堆的根链表头指针操作按阶归并两个树列表类比二进制加法处理进位同阶两树合并堆性质较大根成为较小根的子树输出合并后的堆链表头指针插入insert向堆中插入一个新 key输入堆的根链表头指针的指针、整数 key操作创建单节点 B₀ 堆与原堆执行 merge输出无就地更新根指针查找最小find_min返回堆中所有树的根中最小的 key输入堆的根链表头指针操作遍历所有树的根节点返回最小 key输出最小 key若堆为空返回 INT_MAX删除最小extract_min删除并返回最小 key输入堆的根链表头指针的指针操作找到最小根所在的树将其从链表移除将该树的子树反转后与剩余堆合并输出被删除的最小 key统计节点数size返回堆中节点总数输入堆的根链表头指针操作遍历所有树每棵 Bk 有 2^k 个节点输出节点总数约束条件每棵二项式树的根链表按阶degree从小到大排列每棵树满足最小堆性质父节点 key 子节点 key各阶至多出现一棵树类比二进制各位唯一同阶两树合并时较大 key 的根成为较小 key 的根的子树leftmost child验收标准表格编号测试场景自然语言描述预期结果验证方式1插入序列 [4,1,8,3,7,2]依次 extract_min得到有序序列 1,2,3,4,7,8断言每次 extract_min 结果正确2合并堆 {1,5,9} 和堆 {2,3,8}依次 extract_min得到 1,2,3,5,8,9断言每次结果正确3插入 6 个元素后 size 返回 66断言等于 64插入 1 个元素后 find_min 返回该元素插入值断言5插入 [4,1,8,3,7,2] 后 find_min 返回 11断言等于 16空堆 extract_min 返回 INT_MAXINT_MAX断言7插入 8 个元素N81000₂应只有 B₃堆中只有一棵 degree3 的树断言树链表长度为 18合并两个各含 4 个元素的堆均为 B₂结果为含 8 个元素的 B₃degree3 的树断言C语言实现文件对应文件:binomial_queue.c编译运行:gcc-stdc99-Wall-obinomial_queue_test binomial_queue.c ./binomial_queue_test核心函数:bq_merge(h1, h2)— 合并两个二项式堆返回新链表头bq_insert(heap, key)— 插入 keybq_find_min(heap)— 查找最小值bq_extract_min(heap)— 删除并返回最小值bq_size(heap)— 返回节点总数bq_free(heap)— 释放所有节点内存
