73
правки
Изменения
→extractMinimum
return x;
</pre>
=== extractMinimum extractMin ===
Минимальный элемент хранится в верхнем Bootstrapping, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapping'ов.
<pre>
((y,r), t) = extractMin(q)
return (y, merge(r, t))
</pre>
Здесь <tex>extractMinimumextractMin(q)</tex> {{---}} это функция, извлекающая - минимальный элемент типа Bootstrapping - из приоритетной очереди, она возвращает <tex>(y,r)</tex> - минимальный элемент типа Bootstrapping и остаток от приоритетной очереди после извлечение минимума - <tex>t</tex>. <tex>merge</tex> {{---}} функция, выполняющая слияние двух приоритетных очередей.
Возвращаем Bootstrapping, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.
Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>extractMinimumextractMin</tex> выполняется за <tex>O(log N)</tex>.
== Смотри также ==
* [[Биномиальная куча]]
