Binomial Min Heap删除操作相关测验错题错误原因求解

错误原因解析 #

你选10的核心问题是对二项式最小堆的删除规则理解不到位，忽略了二项堆本身是由多个不同阶的二项树组成，根节点天然是多个的特性：

二项式最小堆删最小节点的固定流程 #

• 第一步：遍历所有二项树的根节点，找到值最小的根，把它从根链表中摘出来
• 第二步：把被删掉的最小根的所有子节点逆序，组成一个新的临时二项堆
• 第三步：把原堆剩下的部分和临时堆合并，同阶的二项树合并（小值当根，大值接成子树），直到所有根的阶数都不重复

本题的具体推导 #

本题里最小的根节点是值为1的节点，移除后它的子节点逆序得到13、10两个临时根，原堆剩下的根还有3、9两个。合并后不存在同阶的二项树，所以最终的根节点有3、9、10、13四个，只有包含至少两个节点的选项才符合要求，单个10显然不符合结构规则。

内容的提问来源于stack exchange，提问作者Hamilton Hardy