Изменения

'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{- --}} основана на использовании [[Персистентная приоритетная очередьБиномиальная куча|персистентных приоритетных очередейбиномиальной кучи]]без каскадных ссылок, добавлении минимального элемента и на идее Data-structural bootstrapping. Поддерживает поиск минимумаПервое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, вставкувторое позволяет получать минимальный элемент за <tex>O(1)</tex>, слияние а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex> в худшем случае и удаление . Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

== Структура ==Используем техникуидею, которую Тарьян называет Bootstrappingи Буксбаум называют Data-structural bootstrapping.

|definition= Bootstrapping '''Data- structural bootstrapping''' {{---}} это техникаидея, позволяющая снизить время <texmath>\mathrm{merge}</texmath> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.

Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</texcode> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так: <tex> '''BPQ''' = '''<T_{min}int, PQ> = '''(T_{min}, PQ<'''BPQ<T_{min}, PQ''')'''>>)''' </texcode>

Куча из одного элемента будет выглядеть создается так:

<texcode>create '''BPQ''' singleton'(x:'''int''') = BPQ: '''return''' <x, null></texcode>

Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex>.

Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> . Этот элемент и добавлением станет вершиной кучи. Это позволит в любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в приоритетную очередь второго Bootstrappingструктуру кучи при помощи операции <math>\mathrm{insert}</math>.<precode> '''BPQ''' merge(('''<'''x:'''int''',q):'''PQ>''', ('''<'''y:'''int''',r:'''PQ>''')): '''if ''' x<y '''return (''' <x, insert(q, (<y,r>)))> '''else''' '''return (''' <y, insert(r, (<x,q>)))></precode>Здесь <texmath>\mathrm{insert}</texmath> это добавление в приоритетную очередь . Если оно работает за <tex>O(1)</tex>, тогда то <texmath>\mathrm{merge}</texmath> работает за <tex>O(1)</tex>. 

Это создание нового Bootstrapping <tex> BPQ </tex> и <texmath>\mathrm{merge}</texmath> его с основным деревом.<precode> '''BPQ''' insert(('''<'''x:'''int''',q):'''PQ>''', y:'''int'''): '''return ''' merge((<x,q)>, createsingleton(y))</precode>Создание и По сути операция <math>\mathrm{insert}</math> - тот же самый <texmath>\mathrm{merge}</texmath> выполняются : создается дерево нулевого ранга за <tex>O(1)</tex>, тогда <tex>insert</tex> работает а затем оно сливается с основным также за <tex>O(1)</tex>. 

Выполняется просто, так как Bootstrapping <tex> BPQ </tex> хранит минимум.<precode> '''int''' getMin(('''<'''x:'''int''',q:'''PQ>''')): '''return ''' x;</precode>Очевидно, работает за <tex>O(1)</tex>.

Минимальный элемент хранится в верхнем Bootstrapping<tex> BPQ </tex>, по этому поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapping'ов, состоящей из <tex> BPQ</tex>. <precode> '''<int, BPQ>''' extractMin(('''<'''x:'''int''',q:'''PQ>''')): (( <<y,r)>, t) > = extractMin(q) '''return (''' <x, <y, merge(r, t))>></precode>Здесь <texmath>\mathrm{extractMin(q)}</texmath> {{---}} это функция, извлекающая - минимальный элемент типа Bootstrapping - <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(\langle y,r)\rangle</tex> {{--- }} минимальный элемент типа Bootstrapping <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{--- }} <tex>t</tex>. Соответственно, <texmath>\mathrm{merge}</texmath> {{---}} функция, выполняющая слияние двух приоритетных очередей.

Возвращаем Bootstrappingминимум и <tex> BPQ </tex>, где <tex>yx</tex> {{---}} новый минимальный элемент, и <texmath>\mathrm{merge}(r, t)</texmath> {{---}} приоритетная очередь без элемента элементов <tex>x</tex> и <tex>y</tex>.

Так как <texmath>\mathrm{extractMin}</texmath> и <texmath>\mathrm{merge}</texmath> выполняются за <tex>O(\log N)</tex>, тогда то <texmath>\mathrm{extractMin}</texmath> выполняется за <tex>O(\log N)</tex>.

== Ссылки Источники информации ==* [http://www.lektorium.tv/lecture/?id=14234 Lektorium {{---}} Лекция А.С. Станкевича по приоритетным очередям]

* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]