Изменения

'''Куча Бродала-Окасаки''' (англ. ''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> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

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

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

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

Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>create(x) = BPQ<x, null>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>. === getMinimum getMin ===Выполняется просто, так как Bootstrapping <tex> BPQ </tex> хранит минимум.<precode>getMinimum( '''int''' getMin('''<'''x:'''int''',q:'''PQ>''')): '''return ''' x;</precode>Очевидно, работает за <tex>O(1)</tex>. === extractMinimum extractMin ===Минимальный элемент хранится в верхнем Bootstrapping<tex> BPQ </tex>, по этому поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapping'ов, состоящей из <tex> BPQ</tex>. <precode>extractMinimum( '''<int, BPQ>''' extractMin('''<'''x:'''int''',q:'''PQ>''')): (( <<y,r)>, t) > = extractMin(q) '''return (''' <x, <y, merge(r, t))>></precode>Здесь <texmath>extractMinimum\mathrm{extractMin}</texmath> {{---}} это функция, извлекающая - минимальный элемент типа Bootstrapping - <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(\langle y,r)\rangle</tex> {{--- }} минимальный элемент типа Bootstrapping <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{- --}} <tex>t</tex>. Соответственно, <texmath>\mathrm{merge}</texmath> {{---}} функция, выполняющая слияние двух приоритетных очередей. Возвращаем минимум и <tex> BPQ </tex>, где <tex>x</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}(r,t)</math> {{---}} приоритетная очередь без элементов <tex>x</tex> и <tex>y</tex>.

Возвращаем Bootstrapping, где Так как <texmath>y\mathrm{extractMin}</texmath> и <math> \mathrm{{---merge}} новый минимальный элемент, и </math> выполняются за <tex>mergeO(r, t\log N)</tex> приоритетная очередь без элемента , то <math>\mathrm{extractMin}</math> выполняется за <tex>yO(\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]