data-structures - 为什么斐波那契堆保留一个全局节点计数器？

Question

我读到斐波那契堆保留一个全局节点计数器，但我不明白为什么。我什至找到了一个有计数器但根本没有使用它的实现。

Answer 1

它是查询“堆中有多少元素？”形式的查询。花费时间 O(1)。如果不缓存此信息，此查询将花费时间 O(n)，因为必须遍历每棵树以计算其包含的节点数。这类似于为什么一些链表实现会保留一个计数器来跟踪节点的数量。

希望这可以帮助！