1632
правки
Изменения
м
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <texcode>T_{min} '''BPQ''' = '''</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <texint, PQ'''('''BPQ''')'''>T_{min}''' </texcode>. Это можно записать так:
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex>Куча из одного элемента создается так:
Куча из одного элемента будет выглядеть так<code> '''BPQ''' singleton'(x:'''int'''): '''return''' <x, null></code>
<tex>create(x) = BPQ \left \langle x, null\right \rangle</tex> Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex>.
rollbackEdits.php mass rollback
'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, что добавлении минимального элемента и на идее Data-structural bootstrapping. Первое позволяет делать <texmath>\mathrm{insert}</texmath> за <tex>O(1)</tex>, добавлении минимального элемента, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, и идеи Dataа третье {{---structural bootstrapping, }} позволяющей выполнить <texmath>\mathrm{merge}</texmath> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
== Структура ==
{{Определение
|neat = 0
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <texmath>\mathrm{merge}</texmath> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
}}
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>:
== Операции ==
=== Merge ===
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> . Этот элемент и добавлением станет вершиной кучи. Это позволит в приоритетную очередь второго BPQлюбой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции <math>\mathrm{insert}</math>.
<code>
'''pairBPQ''' merge(('''<'''x : '''int''', q : '''bpqPQ>''') : , '''pair<''', (y : '''int''', r : '''bpqPQ>''') : '''pairif''') if x < y '''return''' (<x, insert(q, (<y, r>)))> '''else''' '''return''' (<y, insert(r, (<x, q>)))>
</code>
Здесь <texmath>\mathrm{insert}</texmath> это добавление в приоритетную очередь . Если оно работает за <tex>O(1)</tex>, тогда то <texmath>\mathrm{merge}</texmath> работает за <tex>O(1)</tex>.
=== Insert ===
Это создание нового <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>.
=== getMin ===
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<precode> '''int''' getMin(('''<'''x:'''int''',q:'''PQ>''')): '''return ''' x;</precode>Очевидно, работает за <tex>O(1)</tex>.
=== extractMin ===
Минимальный элемент хранится в верхнем <tex> BPQ</tex>, по этому поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди , состоящей из <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> {{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(\langle y,r)\rangle</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. Соответственно, <texmath>\mathrm{merge}</texmath> {{---}} функция, выполняющая слияние двух приоритетных очередей.
Возвращаем минимум и <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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
