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

Мотивация: Почему Кучи Фибоначчи?

прежде чем прыгать в кучи Фибоначчи, вероятно, хорошо изучить, почему мы даже нуждаемся в них в первую очередь. Есть много других типов куч (бинарные кучи и биномиальные кучи, например), так зачем нужен еще один?

основная причина приходит в алгоритм Дейкстры и прим. Оба этих алгоритма графа работают, поддерживая приоритетную очередь, удерживающую узлы с соответствующими приоритетами. Интересно, что эти алгоритмы полагаются на операцию кучи под названием уменьшение-клавиша который принимает запись уже в очереди приоритетов, а затем уменьшает ее ключ (т. е. увеличивает свой приоритет). На самом деле, большая часть времени выполнения этих алгоритмов объясняется количеством раз, когда вы должны вызвать reduce-key. Если бы мы могли построить структуру данных, которая оптимизировала бы ключ уменьшения, мы могли бы оптимизировать производительность этих алгоритмов. В случае двоичной кучи и биномиальной кучи уменьшение ключа занимает время O(log n), где n-количество узлов в очереди приоритетов. Если бы мы могли отбросить это до O (1), то временные сложности алгоритма Дейкстры и Прима алгоритм будет отбрасывать от О(М зарегистрируйте N) до (m + n записей N), которое является асимптотически быстрее, чем раньше. Поэтому имеет смысл попытаться построить структуру данных, которая эффективно поддерживает ключ уменьшения.

есть еще одна причина рассмотреть возможность разработки лучшей структуры кучи. При добавлении элементов в пустую двоичную кучу каждая вставка занимает время O (log n). Это возможно построить двоичную кучу во времени O (n) если мы знаем, что все n элементов заранее, но если элементы приехать в потоке это не возможно. В случае биномиальной кучи вставка n последовательных элементов занимает амортизированное время O(1) каждый, но если вставки чередуются с удалениями, вставки могут в конечном итоге занять Ω (log n) время каждый. Поэтому мы могли бы хотеть искать реализацию очереди приоритетов, которая оптимизирует вставки, чтобы занять время O (1) каждый.

Шаг Первый: Ленивые Биномиальные Кучи

чтобы начать строить кучу Фибоначчи, мы начнем с a биномиальная куча и ее изменение пытаются сделать вставки занимают время O (1). Это не все, что неразумно, чтобы попробовать это - в конце концов, если мы собираемся сделать много вставок и не столько извлекает, имеет смысл оптимизировать вставок.

Если вы помните, биномиальные кучи работают, сохраняя все элементы в куче в коллекции биномиальных деревьев. Биномиальное дерево Порядка n имеет 2ⁿ узлы в нем, а куча-это структуры в виде коллекции биномиальные деревья, которые все подчиняются свойству кучи. Как правило, алгоритм вставки в биномиальную кучу работает следующим образом:

• создать новый одноэлементный узел (это дерево порядка 0).
• если есть дерево, порядка 0:
  • объединить два дерева порядка 0 вместе в дерево порядка 1.
  • если есть дерево порядка 1:
    • объединить два дерева порядка 1 вместе в дерево порядка 2.
    • если есть дерево порядка 2:
    • ...

этот процесс гарантирует, что в каждый момент времени существует не более одного дерева каждого порядка. Поскольку каждое дерево содержит экспоненциально больше узлов, чем его порядок, это гарантирует, что общее количество деревьев невелико, что позволяет быстро запускать очереди (потому что нам не нужно смотреть на слишком много разных деревьев после выполнения шага dequeue-min).

однако это также означает, что наихудшее время выполнения вставки узла в биномиальную кучу-это Θ(log n), потому что у нас могут быть trees(log n) деревья, которые нужно объединить вместе. Эти деревья должны быть объединены вместе только потому, что нам нужно сохранить количество деревьев низким при выполнении шага dequeue, и нет абсолютно никакой пользы в будущих вставках, чтобы сохранить количество деревьев низким.

это вводит первый отход от биномиальных куч:

Модификация 1: когда вставив узел в кучу, просто создайте дерево порядка 0 и добавьте его в существующую коллекцию деревьев. Не объединяйте деревья вместе.

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

Модификация 2: при слиянии двух куч вместе, просто объединить все их деревья вместе, не делая никакого слияния. Не консолидируйте никакие деревья вместе.

Если мы внесем это изменение, мы довольно легко получим O(1) performace на наших операциях очереди, так как все, что мы делаем, это создаем новый узел и добавляем его в коллекцию деревьев. Однако, если мы просто сделайте это изменение и не делайте ничего другого, мы полностью нарушаем производительность операции dequeue-min. Напомним, что dequeue-min должен сканировать корни всех деревьев в куче после удаления минимального значения, чтобы он мог найти наименьшее значение. Если мы добавим узлы Θ(n), вставив их в путь, наша операция удаления из очереди должна будет потратить Θ(n) время на просмотр всех этих деревьев. Это огромный удар по производительности... можем ли мы избежать этого?

Если наши вставки действительно просто добавляют больше деревьев, тогда первый dequeue, который мы делаем, безусловно, займет Ω(n) время. Однако, это не значит, что dequeue должен быть дорогим. Что произойдет, если после выполнения dequeue мы объединим все деревья в куче вместе, так что мы получим только одно дерево каждого порядка? Первоначально это займет много времени, но если мы начнем делать несколько очередей подряд, эти будущие очереди будут значительно быстрее, потому что деревьев меньше валяется где попало.

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

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

• посмотрите вверх и посмотрите, есть ли уже дерево такого порядка.
• если нет, вставьте дерево в хэш-таблице.
• в противном случае:
  • объединить текущее дерево с деревом этого порядка, удалив старое дерево из хэш-таблица.
  • рекурсивно повторить это процесс.

эта операция гарантирует, что когда мы закончим, есть не более одного дерева каждого заказа. Это также относительно эффективно. Предположим, что мы начинаем с T полных деревьев и заканчиваем t полными деревьями. Количество полных слияний, которые мы в конечном итоге сделаем, будет T - t - 1, и каждый раз, когда мы делаем слияние, для этого потребуется время O(1). Таким образом, время выполнения этой операции будет линейным по количеству деревьев (каждое дерево посещается хотя бы один раз) плюс количество выполненных слияний.

Если количество деревьев мало(скажем, Θ(log n)), то эта операция займет только время O (log n). Если число деревьев велико(скажем, Θ(n)), то эта операция займет Θ(n) время, но оставит только trees (log n) деревья, что сделает будущие очереди намного быстрее.

мы можем количественно определить, насколько лучше все будет, сделав амортизированный анализ и используя потенциальную функцию. Пусть Φ - наша потенциальная функция и пусть Φ - количество деревьев в структуре данных. Это означает, что затраты на операции являются следующими:

• вставить: работает ли O(1) и увеличивает потенциал на единицу. Амортизируемая стоимость равна O(1).
• слияние: работает ли O(1). Потенциал одной кучи снижается до 0, а потенциал другой кучи увеличивается на соответствующую величину, поэтому нет чистого изменения потенциала. Амортизированная стоимость таким образом O (1).
• Dequeue-Min: работает ли O(#деревья + #слияния) и уменьшает потенциал до Θ(log n), количество деревьев, которые мы имели бы в биномиальном дереве, если бы мы охотно объединяли деревья вместе. Мы можем объяснить это по-другому. Пусть число деревьев записывается как Θ (log n) + E, где E - "избыточное" число деревьев. В этом случае общая проделанная работа равна Θ(log n + E + #merges). Обратите внимание, что мы сделаем одно слияние на избыточное дерево, и поэтому общая проделанная работа Θ (log n + E). Поскольку наш потенциал уменьшает количество деревьев от Θ(log n) + E до Θ(log n), падение потенциала равно-E. следовательно, амортизированная стоимость dequeue-min равна Θ (log n).

другое интуитивно понятный способ, чтобы увидеть, почему амортизированной стоимости извлечения-мин Θ(зарегистрируйте n), с помощью почему у нас есть лишние деревья. Эти дополнительные деревья есть, потому что эти проклятые жадные вставки делают все эти дополнительные деревья и не платят за них! Мы поэтому можно "вернуть" стоимость, связанную с выполнением всех слияний обратно к отдельным вставкам, которые заняли все это время, оставив позади operation(log n) "основную" операцию и кучу других операций, которые мы будем обвинять в вставках.

таким образом:

модификация 3: при операции dequeue-min консолидируйте все деревья, чтобы обеспечить наличие не более одного дерева каждого заказа.

на данный момент, у нас есть вставки и слияния выполняется за время O(1) амортизированной времени и извлекает работает в o(зарегистрируйте N). Это довольно изящно! Тем не менее, у нас все еще нет работы с уменьшением ключа. Это будет самая сложная часть.

Шаг Второй: Реализация Уменьшения Ключа

прямо сейчас у нас есть" ленивая биномиальная куча", а не куча Фибоначчи. Реальное изменение между биномиальной кучей и кучей Фибоначчи - это то, как мы реализуем ключ уменьшения.

Напомним, что операция уменьшения ключа должна возьмите запись уже в куче (обычно у нас есть указатель на нее) и новый приоритет, который ниже существующего приоритета. Затем он изменяет приоритет этого элемента на новый, более низкий приоритет.

мы можем реализовать эту операцию очень быстро(во времени O (log n)), используя простой алгоритм. Возьмите элемент, ключ которого должен быть уменьшен (который может быть расположен в O(1) времени; помните, мы предполагаем, что у нас есть указатель на него) и понизить его приоритет. Затем, повторно поменять местами он со своим родительским узлом до тех пор, пока его приоритет ниже, чем у его родителя, останавливаясь, когда узел останавливается или когда он достигает корня дерева. Эта операция занимает время O(log n), потому что каждое дерево имеет высоту не более O(log n), и каждое сравнение занимает время O (1).

помните, однако, что мы пытаемся сделать даже лучше, чем это - мы хотим, чтобы время выполнения было O(1)! Это же очень жесткая привязка к матчу. Мы не можем использовать какой-либо процесс, который будет перемещать узел вверх или вниз по дереву, так как эти деревья имеют высоту, которая может быть Ω(log n). Мы должны попробовать что-то более радикальное.

предположим, что мы хотим уменьшить ключевого узла. Единственный способ, которым свойство кучи будет нарушено, - это если новый приоритет узла ниже, чем у его родителя. Если мы посмотрим на поддерево, коренящееся в этом конкретном узле, оно все равно будет подчиняться свойству кучи. Итак, вот совершенно сумасшедшая идея: что, если всякий раз, когда мы уменьшаем ключ узла, мы сокращаем ссылку на родительский узел, а затем принести все поддерево корнями в узле обратно на верхний уровень дерева?

модификация 4: уменьшите-ключ уменьшите ключ узла и, если его приоритет меньше, чем приоритет его родителя, вырежьте его и добавьте в корневой список.

какой будет эффект от этой операции? Произойдет несколько вещей.

1. узел, который ранее имел наш узел в качестве ребенка теперь думает, что он имеет неправильное количество детей. Напомним, что биномиальное дерево Порядка n определяется как имеющее n потомков, но это уже не так.
2. коллекция деревьев в корневом списке будет расти, увеличивая стоимость будущих операций удаления из очереди.
3. деревья в нашей куче не обязательно будут биномиальными деревьями больше. Это могут быть" бывшие " биномиальные деревья, которые теряли детей в разные моменты времени.

число (1) не слишком много проблема. Если мы отрежем узел от его родителя, мы можем просто уменьшить порядок этого узла на один, чтобы указать, что у него меньше детей, чем он думал ранее. Число (2) также не является проблемой. Мы можем просто вернуть дополнительную работу, выполненную в следующей операции dequeue-min, в операцию уменьшения ключа.

число (3) - это очень, очень серьезный вопрос, который нам нужно будет решить. Вот проблема: эффективность биномиальной кучи частично связана с тем, что любой коллекция из n узлов может храниться в коллекции trees (log n) деревьев различного порядка. Причина этого заключается в том, что каждое биномиальное дерево 2ⁿ узлы в нем. Если мы можем начать вырезать узлы из деревьев, то мы рискуем иметь деревья, которые имеют большое количество потомков (то есть высокий порядок), но у которых не так много узлов в них. Например, предположим, что мы начинаем с одного дерева порядка k, а затем выполняем операции с уменьшением ключа на всех внуках k. это оставляет k как a дерево с порядком k, но которое содержит только k + 1 полных узлов. Если мы будем продолжать повторять этот процесс повсюду, мы можем получить кучу деревьев различных порядков, в которых есть очень небольшое количество детей. Следовательно, когда мы делаем нашу операцию объединения, чтобы сгруппировать деревья вместе, мы не можем уменьшить количество деревьев до управляемого уровня, нарушая bound(log n)-временную границу, которую мы действительно не хотим терять.

на данный момент, мы в замешательстве. Нам нужно большая гибкость с тем, как деревья могут быть изменены, чтобы мы могли получить функциональность ключа уменьшения времени O(1), но мы не можем позволить деревьям произвольно изменяться, или мы закончим тем, что амортизированное время выполнения уменьшенного ключа увеличится до чего-то большего, чем O(log n).

необходимое понимание-и, честно говоря, то, что я думаю, является настоящим гением в куче Фибоначчи - это компромисс между ними. Идея заключается в следующем. Если мы срежем дерево от его родителя, мы уже будем планирование уменьшения ранга родительского узла на единицу. Проблема действительно возникает, когда узел теряет много детей, в этом случае его ранг значительно уменьшается без каких-либо узлов в дереве зная об этом. Поэтому мы скажем, что каждый узел может потерять только одного ребенка. Если узел теряет второго ребенка, то мы будем вырезать этот узел из его родителя, который распространяет информацию о том, что узлы отсутствуют выше в дереве.

получается это прекрасный компромисс. Это позволяет нам быстро уменьшать ключи в большинстве контекстов (если узлы не являются потомками одного и того же дерева), и только в редких случаях нам приходится "распространять" ключ уменьшения, вырезая узел из его родителя, а затем вырезая этот узел из его дедушки.

чтобы отслеживать, какие узлы потеряли детей, мы назначим бит "mark" для каждого узла. Каждый узел сначала будет иметь бит метки очищен, но всякий раз, когда он теряет дочерний элемент, он будет иметь бит установлен. Если он теряет второй дочерний элемент после того, как бит уже установлен, мы очистим бит, а затем вырежем узел из его родителя.

модификация 5: назначьте бит метки каждому узлу, который изначально является ложным. Когда ребенок вырезается из немаркированного родителя, отметьте родителя. Когда ребенок вырезается из отмеченного родителя, снимите отметку с родителя и вырежьте родителя из его родителя.

на этот старый вопрос переполнения стека, Я набросал доказательство, которое показывает, что если деревья могут быть изменены таким образом, то любое дерево Порядка n должно содержать по крайней мере Θ(φⁿ) узлы, где φ-это золотой пропорции, около 1.61. Это означает, что число узлов в каждом дереве по-прежнему экспоненциально в порядке дерева, хотя это более низкий показатель раньше. В результате анализ, который мы делали ранее о временной сложности операции уменьшения ключа, все еще сохраняется, хотя термин скрыт в bit (log n) бит будет отличаться.

есть одна очень последняя вещь, чтобы рассмотреть-как насчет сложности уменьшения ключа? Раньше это было O (1), потому что мы просто вырезали дерево, укорененное в соответствующем узле, и переместили его в корневой список. Однако теперь нам, возможно, придется сделать "каскадный разрез", в котором мы вырезаем узел из его родителя, а затем вырезаем это узел его родитель, etc. Как это дает o (1) ключи уменьшения времени?

в наблюдение здесь заключается в том, что мы можем добавить "заряд" к каждой операции уменьшения ключа, которую мы затем можем потратить, чтобы вырезать родительский узел из его родителя. Поскольку мы вырезаем узел только из его родительского узла, если он уже потерял двух детей, мы можем притвориться, что каждая операция с уменьшением ключа оплачивает работу, необходимую для вырезания его родительского узла. Когда мы сокращаем родителя, мы можем списать затраты на это обратно на одну из предыдущих операций с уменьшением ключа. Следовательно, даже если любая индивидуальная операция уменьшения ключа может потребоваться много времени для завершения, мы всегда можем амортизировать работу по более ранним вызовам, чтобы время выполнения амортизировалось O(1).

Шаг Третий: Связанные Списки Предостаточно!

есть одна последняя деталь, о которой мы должны поговорить. Структура данных, которую я описал до сих пор, сложна, но она не кажется катастрофически сложной. Кучи Фибоначчи имеют репутацию страшных... почему?

причина в том, что для осуществления всех операций описанные выше древовидные структуры должны быть реализованы очень умными способами.

Как правило, вы представляете многоходовое дерево либо с помощью каждой родительской точки вниз ко всем дочерним элементам (возможно, с помощью массива дочерних элементов), либо с помощью используя представление левого ребенка / правого брата, где родитель имеет указатель на одного ребенка, который в свою очередь указывает на список других детей. Для биномиальной кучи это идеально. Основную работу мы должны делать на деревьях операция соединения, в которой мы делаем один корневой узел дочерним от другого, поэтому вполне разумно использовать указатели в дереве, направленные от родителей к детям.

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

рассмотрим стандартную представления многоходовых деревьев. Если мы представляем дерево, имея каждый родительский узел хранить массив или список указателей на его дочерние элементы, то мы не можем эффективно (в O(1)) удалить дочерний узел из списка дочерних элементов. Другими словами, во время выполнения для ключа уменьшения будет преобладать бухгалтерский шаг удаления дочернего элемента, а не логический шаг перемещения поддерева в корневой список! Та же проблема возникает в представлении левого ребенка, правого брата.

в решение этой проблемы заключается в том, чтобы хранить дерево странным образом. Каждый родительский узел хранит указатель на один (и произвольный) один из его дочерних узлов. Затем дочерние элементы сохраняются в циклически связанном списке,и каждый из них указывает на своего родителя. Поскольку можно объединить два круговых списка за O(1) Время и вставить или удалить одну запись из одного за O(1) Время, это позволяет эффективно поддерживать необходимое дерево операции:

• сделать одно дерево дочерним от другого: если первое дерево не имеет дочерних элементов, установите его дочерний указатель на второе дерево. В противном случае склейте второе дерево в циклически связанный дочерний список первого дерева.

• удаление дочернего узла из дерева: сращивание этого дочернего узла из связанного списка дочерних узлов для родительского узла. Если это единственный узел, выбранный для представления дочерних элементов родительского узла, выберите один из следующих одноуровневые узлы заменить его (или установить указатель на null, если это последний ребенок.)

есть абсурдно много случаев, чтобы рассмотреть и проверить при выполнении всех этих операций просто из-за количества различных крайних случаев, которые могут возникнуть. Накладные расходы, связанные со всем жонглированием указателями, являются одной из причин, по которой кучи Фибоначчи на практике медленнее, чем их асимптотическая сложность (другая большая-логика удаления минимума значение, для которого требуется вспомогательная структура данных).

модификация 6: используйте пользовательское представление дерева, которое поддерживает эффективное объединение деревьев и вырезание одного дерева из другого.

вывод

Я надеюсь, что этот ответ прольет некоторый свет на тайну, которая является кучей Фибоначчи. Я надеюсь, что вы можете увидеть логическую прогрессию от более простой структуры (биномиальной кучи) к более сложной структуре серией простых шагов, основанных на разумном понимании. Неразумно хотеть сделать вставки амортизированными-эффективными за счет удалений, и точно так же не слишком безумно реализовывать ключ уменьшения, вырезая поддеревья. Оттуда, остальные детали находятся в обеспечении того, что структура по-прежнему эффективна, но они более последствия из других частей, а не причины.

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

надеюсь, что это помогает!