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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> вершин, где <tex> F_k </tex> - <tex> k </tex> число Фибоначчи, определяемое формулой: <tex> F_0 = F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} </tex>
+
Фибоначчиево дерево с вершиной степени <tex> k </tex> содержит не менее <tex> F_k </tex> вершин, где <tex> F_k </tex> {{---}} <tex> k </tex> число Фибоначчи, определяемое формулой: <tex> F_0 = F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} </tex>
 
|proof=
 
|proof=
 
Для вершин со степенью 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.
 
Для вершин со степенью 0 и 1 соответствующие деревья содержат не менее одной вершины, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.
Строка 20: Строка 20:
 
}}
 
}}
  
Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(logN) </tex>. Обозначим эту величину за <tex> D[H] </tex>.
+
Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то максимальная степень вершины в фибоначчиевой куче с <tex> N </tex> вершинами есть <tex> O(\log N) </tex>. Обозначим эту величину за <tex> D[H] </tex>.
  
 
Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).
 
Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).
Строка 47: Строка 47:
 
== Потенциал ==
 
== Потенциал ==
  
Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, где <tex> t[H] </tex> - количество элементов в корневом списке кучи, а <tex> m[H] </tex> - количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> mark[x] == true </tex>). Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.
+
Введем потенциал фибоначчиевой кучи <tex> \Phi(H) = C(t[H] + 2m[H]) </tex>, где <tex> t[H] </tex> {{---}} количество элементов в корневом списке кучи, а <tex> m[H] </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> mark[x] == true </tex>). Подходящую константу <tex> C </tex> выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.
  
 
== Создание кучи ==
 
== Создание кучи ==
  
Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы - <tex> O(1) </tex>.
+
Создается новый пустой корневой список, в <tex> min[H] </tex> устанавливается значение <tex> null </tex>. Реальное время работы {{---}} <tex> O(1) </tex>.
  
 
== Слияние ==
 
== Слияние ==
  
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы - <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>.
  
 
== Вставка элемента ==
 
== Вставка элемента ==
Строка 63: Строка 63:
 
== Извлечение минимума ==
 
== Извлечение минимума ==
  
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> -  максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.
+
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.
  
 
=== "Уплотнение" (Consolidate) ===
 
=== "Уплотнение" (Consolidate) ===
Строка 69: Строка 69:
 
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.
 
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(D[H]) </tex> вершин.
  
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.
+
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.
  
Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]] добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.
+
Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.
  
 
Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:
 
Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:
Строка 92: Строка 92:
 
=== Каскадное вырезание ===
 
=== Каскадное вырезание ===
  
[[File:Cascading-cut.png|thumb|450px|Каскадное вырезание]]
+
[[File:Cascading-cut.png|thumb|600px|Каскадное вырезание]]
  
 
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.
 
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> mark[x] == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.
Строка 98: Строка 98:
 
Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
 
Докажем, что амортизированное время работы операции "уменьшение ключа" есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
  
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2 * k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>. Теперь также стало ясно, для чего в определении нашего потенциала количество вершин с пометкой <tex> mark[x] </tex> учитывается вдвое больше, чем количество вершин в корневом списке.
+
Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой <tex> mark[x] == true </tex> стало на <tex> k </tex> меньше, а в корневом списке прибавилось <tex> k </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2k + O(1)) </tex>. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало <tex> O(1) </tex>. Теперь также стало ясно, для чего в определении нашего потенциала количество вершин с пометкой <tex> mark[x] </tex> учитывается вдвое больше, чем количество вершин в корневом списке.
  
 
На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.
 
На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда <tex> mark[p[x]] == false </tex>, кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.

Версия 00:23, 16 июня 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] F_k [/math][math] k [/math] число Фибоначчи, определяемое формулой: [math] F_0 = F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} [/math]
Доказательство:
[math]\triangleright[/math]

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

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

Оно в худшем случае (удален ребенок со степенью [math] k - 1 [/math]) содержит [math] 1 + F_1 + F_2 + \dots + 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] N [/math] вершинами есть [math] O(\log N) [/math]. Обозначим эту величину за [math] D[H] [/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) = C(t[H] + 2m[H]) [/math], где [math] t[H] [/math] — количество элементов в корневом списке кучи, а [math] m[H] [/math] — количество вершин, у которых удален один ребенок (то есть вершин с пометкой [math] mark[x] == true [/math]). Подходящую константу [math] C [/math] выберем позже, на этапе анализа каскадного вырезания. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.

Создание кучи

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

Слияние

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

Вставка элемента

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

Извлечение минимума

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate ("уплотнение" кучи). Возьмем указатель на [math] min[H] [/math], удалим эту вершину. Ее поддеревья (их не более, чем [math] D[H] [/math], где [math] D[H] [/math] — максимальная степень вершины в куче) все положим в корневой список. Теперь вызываем процедуру [math] Consolidate [/math].

"Уплотнение" (Consolidate)

Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой [math] O(D[H]) [/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]. Докажем это:

Пусть изначально в корневом списке было [math] r [/math] вершин. Тогда в ходе операции [math] Consolidate [/math] мы сделали [math] O(r) [/math] слияний деревьев. Но эти [math] O(r) [/math] слияний скомпенсируются уменьшением потенциала [math] t_i + \Phi_i - \Phi_{i - 1} = r + C(O(D[H]) - r) = O(D[H]) [/math]. Остальных действий будет также [math] O(D[H]) [/math]. Таким образом, учетная стоимость [math] Consolidate: \, O(D[H]) [/math].

На языке метода предоплаты: Положим у каждой вершины-ребенка удаленной монету. Это [math] O(D[H]) [/math] действий. Теперь: у каждой вершины в корневом списке лежит монета, потратим ее на то, чтобы провести процедуру [math] Consolidate [/math]. Получили новый корневой список, снова раздаем монеты каждой вершине. Итого [math] O(D[H]) + O(D[H]) = O(D[H]) [/math] действий.

Уменьшение ключа

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

  1. Проверяем, если новое значение ключа все же меньше значения ключа родителя, то все хорошо, и мы выходим.
  2. Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.

Вырезание вершины

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя ([math] degree[p[x]] [/math]) и снимаем пометку с текущей вершины ([math] mark[x] = false [/math]).

Каскадное вырезание

Каскадное вырезание

Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если [math] mark[x] == false [/math], то мы ставим эту пометку [math] true [/math] и заканчиваем. В противном случае, вырезаем текущую вершину, и запускаем каскадное вырезание от родителя.

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

Пусть мы вызвали процедуру каскадного вырезания [math] k [/math] раз. Тогда вершин с пометкой [math] mark[x] == true [/math] стало на [math] k [/math] меньше, а в корневом списке прибавилось [math] k [/math] новых вершин. Итого, время работы будет: [math] O(k) + \Phi_i - \Phi_{i - 1} = O(k) + C(k - 2k + O(1)) [/math]. Теперь, подбирая соответствующую константу в потенциале, можем добиться того, чтобы амортизированное время работы этой процедуры стало [math] O(1) [/math]. Теперь также стало ясно, для чего в определении нашего потенциала количество вершин с пометкой [math] mark[x] [/math] учитывается вдвое больше, чем количество вершин в корневом списке.

На языке метода предоплаты: Покажем, что взяв в начале 4 монеты, нам хватит этого для выполнения данной операции. Возьмем 4 монеты перед началом уменьшения ключа. Теперь 1 монету потратим на перенос в корневой список и релаксацию минимума, еще 1 - на то, чтобы положить монету у новой вершины в корневом списке. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда [math] mark[p[x]] == false [/math], кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.

Иначе, [math] mark[p[x]] == true [/math] и там лежит 2 монеты. 2 + 2 = 4, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.

На рисунке проиллюстрирован процесс понижения ключа вершины c 10 до 7. Серым помечены вершины с [math] mark[x] == true [/math].

Удаление вершины

Удаление вершины реализуется через уменьшение ее ключа до [math] -\infty [/math] и последующим извлечением минимума. Амортизированное время работы: [math] O(1) + O(D[H]) = O(D[H]) [/math].

Поскольку, ранее мы показали, что [math] D[H] = O(log|H|) = O(logN) [/math], то соответствующие оценки доказаны.

Ссылки