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