69
правок
Изменения
→Операции
== Операции ==
=== 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)))
=== Insert ===
Это создание нового ''BPQ '' и <math>\mathrm{merge}</math> его с основным деревом.
<code>
'''pair(int, bpq)''' insert((x : '''int''', q : '''bpq'''):'''pair''', 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'''):'''pair'''):
return x;
</code>
=== extractMin ===
Минимальный элемент хранится в верхнем ''BPQ'', по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди ''BPQ'''ов.
<code>
'''pair (int, bpq)''' extractMin('''pair'''(x : '''int''', q : '''bpq'''):'''pair'''): ((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>.
