测试斐波那契堆extractMinimum()方法需覆盖哪些边界用例

遗漏的边界测试场景 #

你现有用例已经覆盖了基础的空堆、单节点、多根节点场景，还需要补充以下边界情况：

• 旧最小节点是根列表的头节点/尾节点：验证删除节点、挂载其子节点到根列表的过程中，双向循环链表的首尾引用正常，不会出现断链、遍历死循环问题
• 旧最小节点的子节点本身带有标记位：验证这些子节点被提升到根列表后，标记位按规则全部重置为未标记，不会残留之前的标记状态
• 旧最小节点的子节点携带多层后代（子节点还有自己的子节点）：验证操作过程仅将旧最小的直接子节点挂载到根列表，不会错误篡改孙节点及更深层节点的父子引用、秩（rank）值
• 根列表存在多个与新最小节点key相等的根节点：验证最小指针选取逻辑稳定，不会出现空引用、重复指向问题，只要符合你预先定义的相等值选取规则即可
• 旧最小节点无子女的多根节点场景：对应单节点无子女场景的多根版本，验证删除最小节点后根列表拼接正确，不会残留已删除节点的引用
• 旧最小节点的子节点中存在比剩余原有根节点key更小的值：如果你的实现逻辑是先在剩余原有根节点中找到新最小、再挂载旧最小的子节点，一定要覆盖这个场景，验证挂载完成后是否同步更新了最小指针，避免最小指针没有指向真正的全局最小值
• 空堆连续多次调用extractMinimum()：验证异常处理/返回值逻辑稳定，不会出现内存错误、状态错乱
• 旧最小节点的子节点数量达到堆的预设最大秩：如果你的实现用数组存储秩对应的树节点，验证该场景下不会出现数组越界问题

额外需要补充的校验点 #

除了你已经覆盖的秩计算、根节点标记状态、节点引用校验，还需要增加以下校验维度：

• 双向循环链表完整性校验：每次操作后遍历根列表、每个节点的子节点列表，验证所有节点的prev/next指针可以正常闭环，不存在断链、自环、指向已删除节点的问题，遍历得到的节点总数和堆的实际大小完全一致
• 最小堆性质校验：全量遍历堆中所有节点，验证每个节点的key都小于等于其所有子节点的key，操作过程没有破坏堆的基本性质
• 堆大小计数校验：执行extractMinimum()后，堆的总节点计数要准确减1，不会出现多减、少减的计数错误
• 最小指针有效性校验：操作完成后min指针必须指向根列表中key最小的节点；空堆状态下min指针必须置空
• 标记位规则校验：除了所有根节点必须为未标记状态，还要验证非根节点的标记位没有被错误修改——标记位仅在节点丢失子节点时才会置位，提升子节点到根列表的操作不应该改动非相关节点的标记状态
• 父子引用正确性校验：被提升到根列表的旧最小节点的子节点，其parent指针必须全部置空，不能残留指向已删除旧最小节点的引用；其余未参与移动的节点，其parent/child指针不能被意外篡改
• 根列表顺序校验：由于你的实现明确要求旧最小的子节点要挂载到新最小节点的左侧，需要遍历根列表验证节点顺序符合设计预期，不会出现顺序错乱

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