69
правок
Изменения
Нет описания правки
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.
<code>
'''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''bpqBPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpqBPQ'''<tex> \rangle </tex>):
'''if''' x < y
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.
<code>
'''<tex> \langle </tex>int, bpqBPQ<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpqBPQ'''<tex> \rangle </tex>, y:'''bpqBPQ'''):
'''return''' merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))
</code>
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.
<code>
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''bpqBPQ'''<tex> \rangle </tex>):
'''return''' x
</code>
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>.
<code>
'''<tex> \langle </tex>int, bpqBPQ<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''bpqBPQ'''<tex> \rangle </tex>):
<tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)
'''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex>
