Изменения

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

Используем структуруидею, которую Тарьян называет Bootstrappedи Буксбаум называют Data-structural bootstrapping. Она будет хранить пару из минимального элемента {{Определение|neat = 0|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <texmath>T_\mathrm{minmerge}</math> до <tex> и приоритетную O(1)</tex> путем разрешения хранить в очереди другую очередь Bootstrapped'опов упорядоченную по минимальному элементу. Это можно записать так:}}

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

Слияние возможно выполнить за выполняется выбором минимума из двух значений <tex>O(1)T_{min}</tex> . Этот элемент и станет вершиной кучи. Это позволит в любой момент за счет тогоконстантное время показать его при необходимости. Другой, что второй больший элемент пары это приоритетная очередь, элементами которой являются Bootstrappedбудет вставлен в структуру кучи при помощи операции <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>. 

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

Возвращаем Bootstrapped, где Так как <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]