Фибоначчиева куча — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
'''Фибоначчиевы кучи''' - модификация биномиальных куч, в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость <tex> O(1) </tex>. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций <tex> Extract\_min </tex> и <tex> Delete </tex> значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные <tex> k </tex> - ичные кучи на практике эффективнее.
 +
 
= Фибоначчиевы деревья =
 
= Фибоначчиевы деревья =
 
{{Определение
 
{{Определение
Строка 33: Строка 35:
 
}}
 
}}
  
Фибоначчиевы кучи являются сливаемыми(mergeable) кучами.
+
Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, 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> \Phi_{n + 1} - \Phi_n = 0 </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

Фибоначчиевы кучи - модификация биномиальных куч, в которых всех операции, где не требуется удаление элементов, имеют амортизированную стоимость [math] O(1) [/math]. Также являются сливаемыми кучами("mergeable heap"). Теоретически полезны тогда, когда операций [math] Extract\_min [/math] и [math] Delete [/math] значительно меньше, чем остальных. К сожалению, скрытые константы велики, так что на практике использование фибоначчиевых куч оказывается нецелесообразным: обычные [math] k [/math] - ичные кучи на практике эффективнее.

Фибоначчиевы деревья

Определение:
Фибоначчиево дерево - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.


Лемма:
Фибоначчиево дерево ранга [math] k [/math] содержит не менее [math] F_k [/math] ([math] k [/math] число Фибоначчи) вершин
Доказательство:
[math]\triangleright[/math]

Для рангов 0 и 1 соответствующие деревья содержат 1 вершину, [math] F_0 \ge 1, F_1 \ge 1 [/math].

Рассмотрим дерево ранга [math] k [/math]

Оно в худшем случае (удален ребенок ранка [math] k - 1 [/math]) содержит [math] 1 + F_1 + F_2 + ... + F_{k-2} [/math] вершин.

Эта сумма, в свою очередь, равна [math] F_k [/math]
[math]\triangleleft[/math]

Поскольку [math] F_k = \Omega(\varphi^k) [/math], где [math] \varphi = \frac {1 + \sqrt 5}2 [/math], то высота фибоначчиева дерева есть [math] O(logN) [/math].

Каждая вершина [math] x [/math] знает своего родителя ([math] p[x] [/math]) и какого-нибудь своего ребенка([math] child[x] [/math]).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за [math] O(1) [/math]

Также в любой вершине хранятся поля [math] degree[x], \, mark[x] [/math]: степень вершины(число ее детей) и пометка о том, потеряла ли вершина [math] x [/math] ребенка после того, как она в последний раз сделалась чьим-либо потомком.

Фибоначчиевы кучи

Определение:
Фибоначчиева куча - набор фибоначчиевых деревьев.


Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list). В отличие от биномиальных куч, в корневом списке может находиться несколько деревьев с одной и той же степенью корня.

Доступ к куче осуществляется с помощью указателя [math] min[H] [/math], указывающего на минимальную вершину в куче.

Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью методов амортизационного анализа.

Операции

Потенциал

Введем потенциал фибоначчиевой кучи [math] \Phi(H) = t[H] + 2m[H] [/math], как количество элементов в корневом списке ([math] t[H] [/math]) прибавить удвоенное количество вершин с [math] mark[x] == true \, (m[H]) [/math]. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

Make_heap

Создается новый пустой корневой список, в [math] min[H] [/math] устанавливается значение [math] null [/math]. Реальное время работы - [math] O(1) [/math].

Merge

Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - [math] O(1) [/math]. Амортизированное время работы - также [math] O(1) [/math], поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, [math] \Phi_{n + 1} - \Phi_n = 0 [/math].

Insert

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4.

Extract_min

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи).

Consolidate

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой [math] O(logN) [/math] вершин.

Для этого возьмем массив списков указателей на корни деревьев [math] A[0..D[H]] [/math], где [math] D[H] [/math] - максимальная степень вершины в текущем корневом списке. [math] D[H] = O(logN) [/math].

Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна [math] d [/math] Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна [math] d + 1 [/math]. Продолжаем, пока не найдем свободную ячейку.

Учетная стоимость [math] Consolidate [/math] равна [math] O(D[H]) [/math]. Докажем это: