Изменения

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

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

'''BPQ''' merge'('''<'''x:'''int''', q:'''PQ>''', '''<'''y:'''int''', r:'''PQ>'''):

'''BPQ''' insert'('''<'''x:'''int''', q:'''PQ>''', y:'''int'''): '''return''' merge'(<x, q>, singleton(y))

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

'''int''' getMin('''<tex> \langle </tex>'''x:'''int''', q:'''BPQPQ>'''<tex> \rangle </tex>):

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

'''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' extractMin('''<tex> \langle </tex>'''x:'''int''', q:'''BPQPQ>'''<tex> \rangle </tex>): <tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q) '''return''' <tex> \langle x, </tex>y, merge(r, t)<tex> \rangle </tex>

Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(\langle y,r)\rangle</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. Соответственно, <math>\mathrm{merge}</math> {{---}} функция, выполняющая слияние двух приоритетных очередей.

Возвращаем минимум и <tex> BPQ </tex>, где <tex>yx</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}(r,t)</math> {{---}} приоритетная очередь без элемента элементов <tex>x</tex> и <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 Lektorium {{---}} Лекция А.С. Станкевича по приоритетным очередям]