Структура данных Фибоначчи имеет название "Фибоначчи" в ее имени, но ничто в структуре данных, по-видимому, не использует числа Фибоначчи. Согласно статье Википедии:
Название кучи Фибоначчи происходит от чисел Фибоначчи, которые используются в анализе времени выполнения.
Как эти числа Фибоначчи возникают в куче Фибоначчи?
Куча Фибоначчи состоит из коллекции меньших кучно-упорядоченных деревьев разных "порядков", которые подчиняются определенным структурным ограничениям. Последовательность Фибоначчи возникает потому, что эти деревья построены таким образом, что дерево порядка 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, что имеет смысл, потому что порядок дерева должен быть числом содержащихся в нем детей.
Проблема с этим заключается в том, что если слишком много деревьев обрезается от одного и того же дерева, у нас может быть дерево с большим порядком, но оно содержит очень небольшое число узлов. Гарантии времени кучи Фибоначчи возможны только в том случае, если деревья с большими порядками содержат огромное количество узлов, и если мы можем просто разрезать любые узлы, которые мы хотели бы получить от деревьев, мы могли бы легко попасть в ситуацию, когда дерево с огромным порядком содержит только небольшое число узлов.
Чтобы решить эту проблему, кучи Фибоначчи составляют одно требование - , если вы вырезаете двух детей из дерева, вы должны, в свою очередь, вырезать это дерево из своего родителя. Это означает, что деревья, которые образуют фибоначчи куча не будет слишком сильно повреждена клавишей уменьшения.
И теперь мы можем перейти к части чисел Фибоначчи. На этом этапе мы можем сказать следующее о деревьях в куче Фибоначчи:
Итак, теперь мы можем спросить - каковы минимально возможные деревья, которые вы можете сделать при этих предположениях?
Попробуйте несколько примеров. Существует только одно возможное дерево порядка 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 узлов
Если вам интересно, оригинальная бумага на кучи Фибоначчи имеет фотографии этих мельчайших деревьев. Это довольно изящно, чтобы видеть!
Надеюсь, это поможет!
Я хочу дать интуитивное объяснение, что у меня сам был "Ага!". момент с.
Структуры дерева достигают времени выполнения O (log n), поскольку они могут хранить экспоненциальное количество элементов с точки зрения их высот. Двоичные деревья могут хранить 2 ^ h, трехзначные деревья могут хранить 3 ^ h и т.д. Для x ^ h как общий случай.
Может x быть меньше 2? Конечно, это возможно! До тех пор, пока x > 1, мы все же достигаем времени выполнения журнала и способности хранить экспоненциально большое количество элементов для его высоты. Но как мы строим такое дерево? Куча Фибоначчи представляет собой структуру данных, где x ≈ 1,62, или Золотой коэффициент. Всякий раз, когда мы сталкиваемся с Золотым коэффициентом, есть числа Фибоначчи, которые где-то скрываются...
Куча Фибоначчи - фактически лес деревьев. После процесса, называемого "консолидация", каждый из этих деревьев содержит определенное количество элементов, которые являются точной степенью 2. Например, если ваша куча Фибоначчи имеет 15 элементов, у нее будет 4 дерева, которые будут содержать 1, 2, 4 и 8 пункты соответственно выглядят следующим образом:
Детали процесса "консолидации" не имеют отношения к делу, но по существу они в основном продолжают собирать деревья в лесу одинаковой степени, пока все деревья не имеют разной степени (попробуйте крутая визуализация, чтобы увидеть, как эти деревья создаются). Поскольку вы можете написать любое n как сумму точных степеней 2, легко представить, как консолидированные деревья для кучи Фибоначчи будут выглядеть для любого n.
Хорошо, до сих пор мы до сих пор не видим прямого подключения к номерам Фибоначчи. Где они появляются на фотографии? Они действительно появляются в очень особенном случае, и это также является ключом к тому, почему куча Фибоначчи может предложить O (1) время для операции DECREASE-KEY. Когда мы уменьшаем ключ, если новый ключ по-прежнему больше родительского ключа, нам не нужно ничего делать, потому что свойство min-heap не нарушается. Но если это не так, мы не можем оставить маленького ребенка, погребенного под более крупным родителем, и поэтому нам нужно вырезать его поддерево и вывести из него новое дерево. Очевидно, мы не можем продолжать делать это для каждого удаления, потому что иначе мы получим слишком высокие деревья и больше не будем иметь экспоненциальные элементы, что означает не более O (log n) время для операции извлечения. Итак, вопрос в том, какое правило мы можем настроить таким образом, чтобы у дерева все еще были экспоненциальные элементы для его высоты? Умное понимание таково:
We will allow each parent to loose up to one child. If there is a subsequent attempt to remove another child from same parent then we will cut that parent also out of that tree and put it in root list as tree of 1.
Выше правило гарантирует, что деревья все еще имеют экспоненциальные элементы для своей высоты даже в худшем случае. Что еще хуже? Хуже случается, когда каждый родитель освобождает одного ребенка. Если у родителя есть > 1 ребенок, у нас есть выбор, на который нужно избавиться. В этом случае позвольте избавиться от дочернего с большим поддеревом. Итак, на приведенной выше диаграмме, если вы сделаете это для каждого родителя, у вас будут деревья размером 1, 1, 2 и 3. См. Шаблон здесь? Просто для удовольствия добавьте новое дерево порядка 4 (например, 16 элементов) на диаграмме выше и угадайте, что вы оставите после запуска этого правила для каждого родителя: 5. У нас есть последовательность Фибоначчи здесь!
Поскольку последовательность Фибоначчи экспоненциальна, каждое дерево по-прежнему сохраняет экспоненциальное число элементов и, таким образом, имеет возможность выполнения O (log n) для работы EXTRACT-MIN. Однако обратите внимание, что DECREASE-KEY теперь принимает только O (1). Еще одна интересная вещь заключается в том, что вы можете представить любое число в виде суммы чисел Фибоначчи. Например, 32 = 21 + 8 + 3, что означает, что если вам нужно удерживать 32 элемента в куче Фибоначчи, вы можете сделать это, используя 3 дерева с 21, 8 и 3 предметами соответственно. Однако процесс "консолидации" не создает деревья с числами фибоначчи узлов. Они возникают только тогда, когда происходит этот худший случай DECREASE-KEY или DELETE.
Дальнейшее чтение