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