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

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

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

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

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

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

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

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

• У дерева порядка 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, а два - вторым:

 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} узлов!

Если вам интересно, в оригинальной статье о кучах Фибоначчи есть изображения этих мельчайших деревьев. На это приятно смотреть! Также ознакомьтесь с этот пост по обмену стеками теории CS для альтернативного объяснения того, почему деревья кучи Фибоначчи имеют такие размеры, как и они.

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

Я хочу дать интуитивное объяснение, что у меня самого было «Ага!» момент с.

Древовидные структуры достигают времени выполнения O (log n), потому что они могут хранить экспоненциальное количество элементов с точки зрения их высоты. Бинарные деревья могут хранить 2 ^ h, тройные деревья могут хранить 3 ^ h и так далее для x ^ h как общий случай.

Может ли x быть меньше 2? Конечно, может! Пока x> 1, мы по-прежнему достигаем времени выполнения журнала и способности хранить экспоненциально большое количество элементов для его высоты. Но как построить такое дерево? Куча Фибоначчи - это структура данных, в которой x ≈ 1,62 или золотое сечение. Всякий раз, когда мы сталкиваемся с золотым сечением, где-то скрываются числа Фибоначчи ...

Куча Фибоначчи на самом деле представляет собой лес деревьев. После процесса, называемого «консолидация», каждое из этих деревьев содержит отдельное количество элементов, которые являются точными степенями 2. Например, если ваша куча Фибоначчи имеет 15 элементов, у нее будет 4 дерева, которые содержат 1, 2, 4 и 8. элементы соответственно выглядят так:

Детали процесса «консолидации» не имеют значения, но по сути он в основном поддерживает объединение деревьев в лесу с одинаковой степенью до тех пор, пока все деревья не будут иметь разную степень (попробуйте классная визуализация, чтобы увидеть, как строятся эти деревья). Поскольку вы можете записать любое n как сумму точных степеней двойки, легко представить, как консолидированные деревья для кучи Фибоначчи будут выглядеть для любого 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-ответа прибил его безупречно.