Изменения
Нет описания правки
'''''Куча Бродала-Окасаки''''' (англ. ''Brodal's and Okasaki's Functional Priority Queue'') - основана на использовании персистентных приоритетных очередей. Поддерживает поиск минимума, вставку, слияние за <tex>O(1)</tex> в худшем случае и удаление минимума за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
== Структура ==
Используем структуру, которую Тарьян называет Bootstrapped. Она будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь Bootstrapped'опов ов упорядоченную по минимальному элементу. Это можно записать так:
<tex> BPQ<T_{min}, PQ> = (T_{min}, PQ<BPQ<T_{min}, PQ>>)</tex>
<tex>create(x) = BPQ<x, null></tex>
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру, где каждое . Каждое значение будет храниться где-то в одном из значений <tex>T_{min}</tex>.
== Операции ==
=== Merge ===
Слияние возможно выполнить за выполняется выбором минимума из двух значений <tex>O(1)T_{min}</tex> за счет того, что второй элемент пары это приоритетная и добавлением в приоритетную очередь, элементами которой являются второго Bootstrapped.
<pre>
merge((x,q), (y,r))
</pre>
Создание и <tex>merge</tex> выполняются за <tex>O(1)</tex>, тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
=== Find Min getMinimum ===
Выполняется просто, так как Bootstrapped хранит минимум.
<pre>
return x;
</pre>
=== Delete Min extractMinimum ===Минимальный элемент хранится в верхнем Bootstrapped, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapped'повов.
<pre>
((y,r), t) = extractMin(q)
return (y, merge(r, t))
</pre>
Здесь <tex>extractMinextractMinimum</tex> {{---}} это извлечение минимума функция, извлекающая - минимальный элемент типа Bootstrapped - из приоритетной очереди, она вернет возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа Bootstrapped и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <tex>merge</tex> {{--- }} функция, выполняющая слияние двух приоритетных очередей.
Возвращаем Bootstrapped, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.
== Смотри также ==
* [[Биномиальная куча]]
