Кучи Фибоначчи сложно понять, даже несмотря на то, что CLRS предприняла действительно хорошую попытку понять, как это работает. Но некоторые вопросы мне действительно непонятны:
Спасибо!
Причина выбора потенциальной функции связана с комбинацией различных факторов. Обычно потенциал выбирается как t + 2m, где t — количество деревьев, а m — количество отмеченных узлов. Мы можем проанализировать эти части отдельно.
Во-первых, потенциальная функция включает член t, потому что шаг удаления-минимума работает путем многократного слияния вместе разных деревьев в связанном списке. Время, необходимое для этого, зависит от количества имеющихся деревьев, и каждая итерация уменьшает количество деревьев до числа, равного примерно O(log n), где n — количество узлов в куче. Если потенциальная функция включает член t, работа, проделанная для свертывания всех деревьев, может быть перенесена на более ранние операции, которые в первую очередь добавляли деревья в этот список.
Потенциальная функция включает член 2m по той же причине. Когда мы вызываем ключ уменьшения, мы вырезаем узел из его родителя, а затем помечаем родителя. Если родитель уже был отмечен, мы вырезаем его, а затем отмечаем и его родителя. Объем проделанной здесь работы пропорционален длине пути, по которому мы продолжаем вырезать узлы, но затем он снимает пометки со всех задействованных узлов. Следовательно, если у нас есть потенциальная функция, учитывающая количество отмеченных узлов, то мы можем сказать, что, хотя одна длинная серия разрезов может быть дорогостоящей, эта работа может быть перенесена на более ранние операции и распределена более равномерно. Причина, по которой этот член равен 2m, а не m, заключается в том, что, когда мы уменьшаем потенциал, уменьшая количество вырезанных узлов, мы также увеличиваем потенциал t, добавляя больше деревьев обратно в связанный список. Говоря, что каждое падение в отмеченном узле уменьшает потенциал на два, чистое падение потенциала от разреза равно -1, поэтому мы можем отнести будущий шаг слияния к этому уменьшению.
Что касается того, почему мы вообще делаем маркировку - это в основном для того, чтобы математика работала правильно при определении количества и размера деревьев, которые могут остаться в куче Фибоначчи. Можно утверждать, что это был настоящий гениальный шаг, необходимый для того, чтобы придумать кучу Фибоначчи. По сути, если вы можете вырезать слишком много дочерних элементов из каждого дерева, то куча теряет баланс, а если вы не можете вырезать достаточно, вы не можете эффективно реализовать ключ уменьшения. Нахождение баланса между высказыванием «вы можете потерять одного ребенка» является хорошим компромиссом и позволяет получить очень хороший результат в математике.
Надеюсь это поможет!
