Ответ 1
Куча Фибоначчи состоит из коллекции меньших кучно-упорядоченных деревьев разных "порядков", которые подчиняются определенным структурным ограничениям. Последовательность Фибоначчи возникает потому, что эти деревья построены таким образом, что дерево порядка n имеет в нем не менее F n + 2 узлов, где F n + 2 число (n + 2) nf Фибоначчи.
Чтобы понять, почему этот результат верен, давайте начнем с того, как будут построены деревья в куче Фибоначчи. Изначально, всякий раз, когда node помещается в кучу Фибоначчи, он помещается в дерево порядка 0, содержащее только это node. Всякий раз, когда значение удаляется из кучи Фибоначчи, некоторые деревья в куче Фибоначчи объединяются вместе, так что количество деревьев не увеличивается слишком сильно.
При объединении деревьев вместе куча Фибоначчи объединяет только деревья того же порядка. Чтобы объединить два дерева порядка n в дерево порядка n + 1, куча Фибоначчи принимает значение, которое из двух деревьев имеет большее значение корня, чем другое, затем делает это дерево дочерним по отношению к другому дереву. Одним из следствий этого факта является то, что деревья порядка n всегда имеют ровно n детей.
Основная привлекательность кучи Фибоначчи заключается в том, что она эффективно поддерживает снижающий ключ (в амортизированном O (1)). Чтобы поддержать это, куча Фибоначчи реализует уменьшающий ключ следующим образом: чтобы уменьшить ключ значения, хранящегося в некотором node, node вырезается из его родительского дерева и рассматривается как его собственное отдельное дерево. Когда это произойдет, порядок его старого родителя node уменьшается на единицу. Например, если дерево порядка 4 имеет дочерний разрез, он сжимается до дерева порядка 3, что имеет смысл, потому что порядок дерева должен быть числом содержащихся в нем детей.
Проблема с этим заключается в том, что если слишком много деревьев обрезается от одного и того же дерева, у нас может быть дерево с большим порядком, но оно содержит очень небольшое число узлов. Гарантии времени кучи Фибоначчи возможны только в том случае, если деревья с большими порядками содержат огромное количество узлов, и если мы можем просто разрезать любые узлы, которые мы хотели бы получить от деревьев, мы могли бы легко попасть в ситуацию, когда дерево с огромным порядком содержит только небольшое число узлов.
Чтобы решить эту проблему, кучи Фибоначчи составляют одно требование - , если вы вырезаете двух детей из дерева, вы должны, в свою очередь, вырезать это дерево из своего родителя. Это означает, что деревья, которые образуют фибоначчи куча не будет слишком сильно повреждена клавишей уменьшения.
И теперь мы можем перейти к части чисел Фибоначчи. На этом этапе мы можем сказать следующее о деревьях в куче Фибоначчи:
- Дерево порядка n имеет ровно n детей.
- Деревья порядка n формируются путем взятия двух деревьев порядка n - 1 и превращения одного из потомков другого.
- Если дерево теряет двух детей, это дерево отрезано от его родителя.
Итак, теперь мы можем спросить - каковы минимально возможные деревья, которые вы можете сделать при этих предположениях?
Попробуйте несколько примеров. Существует только одно возможное дерево порядка 0, которое представляет собой единственный единственный node:
Smallest possible order 0 tree: *
Наименьшее возможное дерево порядка 1 должно быть как минимум node с ребенком. Самый маленький возможный ребенок, который мы могли бы сделать, - это единственный node с наименьшим деревом порядка-0 в качестве дочернего элемента, который является этим деревом:
Smallest possible order 1 tree: *
|
*
Как насчет наименьшего дерева порядка 2? Здесь все становится интересным. Это дерево, разумеется, должно иметь двух детей, и оно будет образовано путем слияния двух деревьев порядка 1. Следовательно, у дерева первоначально было бы двое детей - дерево порядка 0 и дерево порядка 1. Но помните - мы можем вырезать детей из деревьев после их слияния! В этом случае, если мы срезаем дочерний элемент дерева порядка 1, мы будем иметь дерево с двумя дочерними элементами, каждое из которых является деревьями порядка 0:
Smallest possible order 2 tree: *
/ \
* *
Как насчет порядка 3? Как и раньше, это дерево было бы создано путем слияния двух деревьев порядка 2. Затем мы попытались бы отрезать как можно больше поддеревьев этого дерева порядка-3. Когда он создается, дерево имеет поддеревья заказов 2, 1 и 0. Мы не можем отрезать от дерева порядка 0, но мы можем вырезать одного ребенка из порядка 2 и дерева заказа 1. Если мы это сделаем, мы останемся с деревом с тремя детьми, одним из порядка 1 и двумя из второго порядка:
Smallest possible order 3 tree: *
/|\
* * *
|
*
Теперь мы можем определить шаблон. Наименьшее возможное дерево порядка (n + 2) будет сформировано следующим образом: начните с создания дерева нормального порядка (n + 2), у которого есть дочерние порядки n + 1, n, n - 1,..., 2, 1, 0. Затем сделайте эти деревья как можно меньше, отсекая узлы из них, не вырезая двух детей из того же node. Это оставляет дерево с детьми порядков n, n - 2,..., 1, 0 и 0.
Теперь мы можем написать рекуррентное отношение, чтобы попытаться определить, сколько узлов находится в этих деревьях. Если мы это сделаем, мы получим следующее: где NC (n) представляет наименьшее число узлов, которые могут быть в дереве порядка n:
NC(0) = 1
NC(1) = 2
NC(n + 2) = NC(n) + NC(n - 1) + ... + NC(1) + NC(0) + NC(0) + 1
Здесь последний +1 учитывает сам root node.
Если разложить эти члены, получим следующее:
NC(0) = 1
NC(1) = 2
NC(2) = NC(0) + NC(0) + 1 = 3
NC(3) = NC(1) + NC(0) + NC(0) + 1 = 5
NC(4) = NC(2) + NC(1) + NC(0) + NC(0) + 1 = 8
Если вы заметите, это точно серия Фибоначчи, смещенная двумя позициями. Другими словами, каждое из этих деревьев должно содержать в себе как минимум F n + 2 узлы, где F n + 2 - число (n + 2) nd Фибоначчи.
Так почему же это называется кучей Фибоначчи? Поскольку каждое дерево порядка n должно содержать в нем не менее F n + 2 узлов
Если вам интересно, оригинальная бумага на кучи Фибоначчи имеет фотографии этих мельчайших деревьев. Это довольно изящно, чтобы видеть!
Надеюсь, это поможет!
