Почему куча Фибоначчи называется кучей Фибоначчи?

Question

Структура данных кучи Фибоначчи имеет в своем названии слово "Фибоначчи", но ничто в структуре данных, похоже, не использует числа Фибоначчи. Согласно статье в Википедии:

Название кучи Фибоначчи происходит от чисел Фибоначчи, которые используются в анализе времени выполнения.

Как эти числа Фибоначчи возникают в куче Фибоначчи?

Answer 1

Куча Фибоначчи состоит из набора более мелких упорядоченных кучи деревьев разных "порядков", которые подчиняются определенным структурным ограничениям. Последовательность Фибоначчи возникает потому, что эти деревья построены таким образом, что дерево порядка n имеет по крайней мере F_{n + 2} узлов в нем, где F_{n + 2} - это (n + 2) -ое число Фибоначчи.

Чтобы понять, почему этот результат верен, давайте начнем с того, как строятся деревья в куче Фибоначчи. Первоначально всякий раз, когда узел помещается в кучу Фибоначчи, он помещается в дерево порядка 0, которое содержит только этот узел. Всякий раз, когда значение удаляется из кучи Фибоначчи, некоторые деревья в куче Фибоначчи объединяются вместе, так что количество деревьев не становится слишком большим.

При объединении деревьев куча Фибоначчи объединяет только деревья одного порядка. Чтобы объединить два дерева порядка n в дерево порядка n + 1, куча Фибоначчи принимает то, какое из двух деревьев имеет большее корневое значение, чем другое, и делает это дерево дочерним для другого дерева. Одним из следствий этого факта является то, что деревья порядка n всегда имеют ровно n детей.

Главная привлекательность кучи Фибоначчи состоит в том, что она эффективно поддерживает клавишу уменьшения (в амортизированном O(1)). Чтобы поддержать это, куча Фибоначчи реализует ключ уменьшения следующим образом: чтобы уменьшить ключ значения, хранящегося в некотором узле, этот узел вырезается из его родительского дерева и обрабатывается как его собственное отдельное дерево. Когда это происходит, порядок его старого родительского узла уменьшается на единицу. Например, если у дерева порядка 4 вырезан дочерний элемент, оно сжимается до дерева порядка 3, что имеет смысл, поскольку предполагается, что порядок дерева равен числу дочерних элементов, которые в нем содержатся.

Проблема в том, что если из одного и того же дерева будет отрезано слишком много деревьев, у нас может быть дерево с большим порядком, но содержащее очень небольшое количество узлов. Временные гарантии кучи Фибоначчи возможны только в том случае, если деревья с большими порядками содержат огромное количество узлов, и если мы можем просто вырезать любые деревья, которые нам нужны, из деревьев, мы можем легко попасть в ситуацию, когда дерево с огромным порядком содержит только небольшое количество узлов.

Чтобы решить эту проблему, кучи Фибоначчи предъявляют одно требование - если вы вырезаете двух дочерних элементов из дерева, вы должны в свою очередь вырезать это дерево из его родительского элемента. Это означает, что деревья, которые образуют кучу Фибоначчи, не будут сильно повреждены ключом уменьшения.

И теперь мы можем перейти к части о числах Фибоначчи. На данный момент мы можем сказать следующее о деревьях в куче Фибоначчи:

• Дерево порядка n имеет ровно n детей.
• Деревья порядка n формируются путем взятия двух деревьев порядка n - 1 и превращения одного из детей в другого.
• Если дерево теряет двух детей, оно обрезается от своего родителя.

Итак, теперь мы можем спросить - какие самые маленькие деревья вы можете сделать при этих предположениях?

Давайте попробуем несколько примеров. Существует только одно возможное дерево порядка 0, представляющее собой всего один узел:

Smallest possible order 0 tree:      *

Наименьшее возможное дерево порядка 1 должно быть хотя бы узлом с дочерним элементом. Наименьший возможный дочерний элемент, который мы можем сделать, - это один узел с наименьшим дочерним деревом порядка 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 и двумя из порядка 2:

 Smallest possible order 3 tree:       *
                                      /|\
                                     * * *
                                     |
                                     *

Теперь мы можем определить шаблон. Дерево наименьшего возможного порядка (n + 2) будет сформировано следующим образом: начнем с создания дерева нормального порядка (n + 2), у которого есть дочерние элементы порядков n + 1, n, n - 1, ..., 2, 1, 0. Затем сделайте эти деревья настолько маленькими, насколько это возможно, отрезав от них узлы, не вырезая двух дочерних элементов из одного узла. Это оставляет дерево с детьми порядка 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 отвечает за сам корневой узел.

Если мы расширим эти условия, мы получим следующее:

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) -ое число Фибоначчи.

Так почему же это называется куча Фибоначчи? Потому что в каждом дереве порядка n должно быть не менее F_{n + 2} узлов!

Если вам интересно, в оригинальной статье о кучах Фибоначчи есть фотографии этих наименьших возможных деревьев. Это очень красиво, чтобы увидеть!

Надеюсь это поможет!

Answer 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.

дальнейшее чтение

• Биноминальная куча - кучи Фибоначчи по сути являются ленивыми биномиальными кучами. Это классная структура данных, потому что она показывает другой способ хранения экспоненциальных элементов в дереве для его высоты, отличной от двоичной кучи.
• Интуиция за кучами Фибоначчи Обязательное чтение для всех, кто хочет понять кучи Фибоначчи по своей сути. Учебники часто либо слишком мелкие, но и слишком загроможденные на эту тему, но автор этого SO ответа прибил его к рукам.