Фибоначчиева куча — различия между версиями
Строка 1: | Строка 1: | ||
+ | '''Фибоначчиевы кучи''' - модификация биномиальных куч, в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее. | ||
+ | |||
= Фибоначчиевы деревья = | = Фибоначчиевы деревья = | ||
{{Определение | {{Определение | ||
Строка 33: | Строка 35: | ||
}} | }} | ||
− | + | Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня. | |
− | |||
− | Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). | ||
Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче. | Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче. | ||
Строка 45: | Строка 45: | ||
== Потенциал == | == Потенциал == | ||
− | Введем потенциал фибоначчиевой кучи <tex> \Phi(H) </tex>, как количество элементов в корневом списке прибавить удвоенное количество вершин с <tex> mark[x] == true </tex>. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты. | + | Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = t[H] + 2m[H] </tex>, как количество элементов в корневом списке (<tex> t[H] </tex>) прибавить удвоенное количество вершин с <tex> mark[x] == true \, (m[H]) </tex>. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты. |
== Make_heap == | == Make_heap == | ||
Строка 53: | Строка 53: | ||
== Merge == | == Merge == | ||
− | Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы суммируются | + | Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <tex> O(1) </tex>. Амортизированное время работы - также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>. |
== Insert == | == Insert == | ||
Строка 67: | Строка 67: | ||
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(logN) </tex> вершин. | Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(logN) </tex> вершин. | ||
− | Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. | + | Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. <tex> D[H] = O(logN) </tex>. |
+ | |||
+ | Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex> Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку. | ||
+ | |||
+ | Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это: |
Версия 05:24, 7 июня 2011
Фибоначчиевы кучи - модификация биномиальных куч, в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость
. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций и значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные - ичные кучи на практике эффективнее.Содержание
Фибоначчиевы деревья
Определение: |
Фибоначчиево дерево - биномиальное дерево, где у каждой вершины удалено не более одного ребенка. |
Лемма: |
Фибоначчиево дерево ранга содержит не менее ( число Фибоначчи) вершин |
Доказательство: |
Для рангов 0 и 1 соответствующие деревья содержат 1 вершину, .Рассмотрим дерево ранга Оно в худшем случае (удален ребенок ранка Эта сумма, в свою очередь, равна ) содержит вершин. |
Поскольку
, где , то высота фибоначчиева дерева есть .Каждая вершина
знает своего родителя ( ) и какого-нибудь своего ребенка( ).Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за
Также в любой вершине хранятся поля
: степень вершины(число ее детей) и пометка о том, потеряла ли вершина ребенка после того, как она в последний раз сделалась чьим-либо потомком.Фибоначчиевы кучи
Определение: |
Фибоначчиева куча - набор фибоначчиевых деревьев. |
Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.
Доступ к куче осуществляется с помощью указателя
, указывающего на минимальную вершину в куче.Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.
Операции
Потенциал
Введем потенциал фибоначчиевой кучи
, как количество элементов в корневом списке ( ) прибавить удвоенное количество вершин с . На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.Make_heap
Создается новый пустой корневой список, в
устанавливается значение . Реальное время работы - .Merge
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы -
. Амортизированное время работы - также , поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, .Insert
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.
Extract_min
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи).
Consolidate
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой
вершин.Для этого возьмем массив списков указателей на корни деревьев
, где - максимальная степень вершины в текущем корневом списке. .Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна
Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна . Продолжаем, пока не найдем свободную ячейку.Учетная стоимость
равна . Докажем это: