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