1632
правки
Изменения
м
Создание и По сути операция <math>\mathrm{insert}</math> - тот же самый <math>\mathrm{merge}</math> выполняются : создается дерево нулевого ранга за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает а затем оно сливается с основным также за <tex>O(1)</tex>.
rollbackEdits.php mass rollback
== Операции ==
=== Merge ===
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> . Этот элемент и добавлением станет вершиной кучи. Это позволит в приоритетную очередь второго любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции <texmath> BPQ \mathrm{insert}</texmath>.
<code>
'''BPQ''' merge('''<'''x:'''int''', q:'''PQ>''', '''<'''y:'''int''', r:'''PQ>'''):
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.
<code>
'''BPQ''' insert'('''<'''x:'''int''', q:'''PQ>''', y:'''int'''): '''return''' merge'(<x, q>, singleton'(y))
</code>
=== getMin ===
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.
<code>
'''int''' getMin'('''<'''x:'''int''', q:'''PQ>'''):
'''return''' x
</code>
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>.
<code>
'''<int, BPQ>''' extractMin'('''<'''x:'''int''', q:'''PQ>'''):
<<y, r>, t> = extractMin(q)
'''return''' <x, <y, merge(r, t)>>
