Почему куча Фибоначчи хранит глобальный счетчик узлов?

Question

Я читал, что в куче Фибоначчи хранится глобальный счетчик узлов, но я не понимаю, почему. Я даже нашел реализацию, которая имела счетчик, но не использовал его вообще.

Answer 1

Это сделать запросы вида "сколько элементов в куче?" занять время O(1). Без кеширования этой информации этот запрос занял бы время O(n), так как каждое дерево пришлось бы обходить, чтобы подсчитать, сколько узлов оно содержит. Это похоже на то, почему в некоторых реализациях связанных списков счетчик отслеживает количество узлов.

Надеюсь это поможет!