Просмотр исходного текста страницы Куча Бродала-Окасаки

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

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





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

<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>

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

<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex>

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

== Операции ==
=== Merge ===
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ.
<code>
 '''pair(int, bpq)''' merge((x : '''int''', q : '''bpq''') : '''pair''', (y : '''int''', r : '''bpq''') : '''pair'''):
     '''if''' x < y
         '''return''' (x, insert(q, (y, r)))
     '''else'''
         '''return''' (y, insert(r, (x, q)))
</code>
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.

=== Insert ===
Это создание нового BPQ и <math>\mathrm{merge}</math> его с основным деревом.
<code>
 '''pair(int, bpq)''' insert((x : '''int''', q : '''bpq'''), y : '''bpq'''):
     return merge((x,q), create(y))
</code>
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.

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

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

Возвращаем BPQ, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.

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

== Смотри также ==
* [[Биномиальная куча]]
* [[Очередь]]
* [[Персистентная очередь]]
* [[Персистентная приоритетная очередь]]

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

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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]