Изменения

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

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

<texcode> '''BPQ \left \langle T_{min}''' = '''<int, PQ \right \rangle = '''(T_{min}, PQ \left \langle '''BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle''')'''>''' </texcode>

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

<math> \mathrm{create} </math><texcode> '''BPQ''' singleton'(x:'''int''') = BPQ \left \langle : '''return''' <x, null\right \rangle></texcode>

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

Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> . Этот элемент и добавлением станет вершиной кучи. Это позволит в приоритетную очередь второго BPQлюбой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции <math>\mathrm{insert}</math>.

'''pair(int, bpq)BPQ''' merge(('''<'''x : '''int''', q : '''bpqPQ>''') : , '''pair<''', (y : '''int''', r : '''bpqPQ>''') : '''pair''')

'''return''' (<x, insert(q, (<y, r>)))>

'''return''' (<y, insert(r, (<x, q>)))>

Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь . Если оно работает за <tex>O(1)</tex>, тогда то <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.

Это создание нового <tex> BPQ </tex> и <texmath>\mathrm{merge}</texmath> его с основным деревом.

'''pair(int, bpq)BPQ''' insert(('''<'''x : '''int''', q : '''bpqPQ>'''), y : '''bpqint'''): '''return ''' merge((<x,q)>, createsingleton(y))

Создание и По сути операция <texmath>\mathrm{insert}</math> - тот же самый <math>\mathrm{merge}</texmath> выполняются : создается дерево нулевого ранга за <tex>O(1)</tex>, тогда <tex>insert</tex> работает а затем оно сливается с основным также за <tex>O(1)</tex>.

Выполняется просто, так как <tex> BPQ </tex> хранит минимум.

'''int''' getMin(('''<'''x : '''int''', q : '''bpqPQ>''')): '''return ''' x;

Очевидно, работает за <tex>O(1)</tex>.

Минимальный элемент хранится в верхнем <tex> BPQ</tex>, по этому поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди , состоящей из <tex> BPQ'ов</tex>.

'''pair (<int, bpq)BPQ>''' extractMin('''pair<'''(x : '''int''', q : '''bpqPQ>''')): ((<<y,r)>, t) > = extractMin(q) '''return''' (<x, <y, merge(r, t))>>

Здесь <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 {{---}} Лекция А.С. Станкевича по приоритетным очередям]