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