Ответ 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг второй: реализация ключа уменьшения

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

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

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

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

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

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

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

node, который ранее имел наш node как ребенок, теперь думает, что у него неправильное количество детей. Напомним, что биномиальное древо порядка n определено как имеющее n детей, но это уже не так.
Коллекция деревьев в корневом списке будет расти, увеличивая стоимость будущих операций dequeue.
Деревья в нашей куче не обязательно будут биномиальными деревьями. Они могут быть "ранее" биномиальными деревьями, которые потеряли детей в разные моменты времени.

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

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

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

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

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

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

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

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

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

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

Шаг третий: Связанные списки изобилуют!

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

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

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

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

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

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

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

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

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

Заключение

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

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

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