18
правок
Изменения
м
Создание и По сути операция <math>\mathrm{insert}</math> - тот же самый <math>\mathrm{merge}</math> выполняются : создается дерево нулевого ранга за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает а затем оно сливается с основным также за <tex>O(1)</tex>.
→Insert: Typo
== Операции ==
=== Merge ===
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> . Этот элемент и добавлением станет вершиной кучи. Это позволит в приоритетную очередь второго любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции <texmath> BPQ \mathrm{insert}</texmath>.
<code>
'''BPQ''' merge'('''<'''x:'''int''', q:'''PQ>''', '''<'''y:'''int''', r:'''PQ>'''):
'''if''' x < y
'''return''' <x, insert(q, <y, r>)>
Это создание нового <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)>>
== Источники информации ==
* [http://www.lektorium.tv/lecture/?id=14234 Lektorium {{---}}Лекция А.С. Станкевича по приоритетным очередям]
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]
