Продвиньте узел после того, как уже потеряли 2 или более детей
В decrease-key операция кучи Фибоначчи, если она может потерять s > 1 потомки, прежде чем вырезать узел и объединить его с корневым списком (продвинуть узел), это изменит общую сложность во время выполнения? Я думаю, что нет никаких изменений в сложности, так как изменение в потенциале будет таким же. Но я не уверен, прав ли я.
И как это может быть подтверждено амортизированным анализом?
1 ответ
Изменение числа дочерних элементов, которое может потерять узел в куче Фибоначчи , влияет на время выполнения, но я подозреваю, что если вы будете осторожны с тем, как вы это делаете, вы все равно получите такую же асимптотическую среду выполнения.
Вы правы, что потенциальная функция останется неизменной, если вы позволите каждому узлу потерять несколько дочерних элементов перед возвратом в корень. Тем не менее, потенциальная функция не является источником эффективности кучи Фибоначчи. Причина, по которой мы выполняем каскадные сокращения (перевод нескольких узлов обратно на корневой уровень во время ключа уменьшения), состоит в том, чтобы гарантировать, что дерево, имеющее порядок n, имеет количество узлов, которое экспоненциально по n. Таким образом, при выполнении операции dequeue-min и объединении деревьев таким образом, что существует не более одного дерева каждого порядка, общее количество деревьев, необходимое для хранения всех узлов, является логарифмическим по числу узлов. Стандартная схема маркировки гарантирует, что каждое дерево порядка n имеет не менее Θ (φn) узлов, где φ - Золотое сечение (около 1.618...)
Если вы разрешите удаление большего количества узлов из каждого дерева перед возвратом их в корень, я подозреваю, что если вы ограничите число пропущенных потомков некоторой константой, вы все равно получите те же асимптотические временные границы, но, вероятно, с более высокий постоянный коэффициент (потому что каждое дерево содержит меньше узлов и, следовательно, потребуется больше деревьев). Возможно, стоит написать математику, чтобы увидеть, какое отношение рекуррентности вы получите для числа узлов в каждом дереве, если вам нужно точное значение.
Надеюсь это поможет!