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