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