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