Какова интуиция за структурой данных кучи Фибоначчи?

Question

Я прочитал статью в Википедии о кучах Фибоначчи и прочитал описание структуры данных в CLRS, но они не дают интуитивного представления о том, почему эта структура данных работает. Почему кучи Фибоначчи спроектированы такими, какие они есть? Как они работают?

Спасибо!

Answer 1

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

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

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

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

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

Шаг первый: Ленивые биномиальные кучи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Следовательно:

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

На этом этапе мы имеем операции вставки и слияния, выполняемые во время O(1), и очереди, работающие в амортизированное время O(log 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) также не является проблемой. Мы можем просто перезагружать дополнительную работу, выполненную в следующей операции с минимальными затратами, на операцию нажатия клавиши.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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