删除元素后，擦除操作是否也会更新堆？
我在 fibonacci_heap 的 boost 文档中浏览了成员函数解释，其中提到了增加/减少操作后会发生什么，但是当谈到擦除时，唯一说明的是它擦除了句柄指向的元素。
这是否意味着堆在那之后被改革了？如果没有，被擦除节点的子节点会发生什么？我错过了一些明显的东西吗？
问问题
612 次
1 回答
4
当从斐波那契堆中删除一个元素时，树会被重新合并。作为一般规则，当斐波那契堆上的操作的摊销时间为 O(log(N)) 时，就会发生树合并。
从概念上讲，删除操作可以被认为是两个操作的组合：
- 对于最小堆实现，Delete 是 Decrease-Key (O(1)) 和 Extract-Min (O(log(n)) 的组合。
- 对于最大堆实现，Delete 是增加键 (O(1)) 和提取最大值 (O(log(n)) 的组合。
在实践中，通常会优化实现以避免不必要的步骤，但摊销对数复杂度保持不变。对于 Boost.Heap 的fibonacci_heap::erase()实现：
于 2015-03-10T16:28:39.207 回答