Изменения

Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>.

'''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' extractMin'('''<tex> \langle </tex>'''x:'''int''', q:'''BPQPQ>'''<tex> \rangle </tex>): <tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q) '''return''' <tex> \langle x, </tex>y, merge(r, t)<tex> \rangle </tex>

Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(\langle y,r)\rangle</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. Соответственно, <math>\mathrm{merge}</math> {{---}} функция, выполняющая слияние двух приоритетных очередей.

Возвращаем минимум и <tex> BPQ </tex>, где <tex>yx</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}(r,t)</math> {{---}} приоритетная очередь без элемента элементов <tex>x</tex> и <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>.