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