Изменения

Работает так же как и в эфемерной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. <code> '''function''' extractMinimum(t : '''PersistentBinomialHeap'''): tmp = t minimum = t '''while''' tmp != ''null'' '''if''' minimum.key > tmp.key min = tmp tmp = tmp.next; tmp = t H = PersistentBinomialHeap() tmpNewRoot = H '''while''' tmp != ''null'' '''if''' tmp.next == min tmpNewRoot = PersistentBinomialHeap(tmp) tmpNewRoot.next = tmp.next.next '''else''' tmpNewRoot = PersistentBinomialHeap(tmp) tmpNewRoot = tmpNewRoot.next <font color = "green">//расставляем детей в удаленном дереве в возрастающем порядке с помощью вспомогательного массива nodes</font> H' = PersistentBinomialHeap() tmp = min.child x = 0 '''while''' tmp != ''null'' nodes[x] = tmp tmp = tmp.next x = x + 1 tmp = H' '''for''' i = x - 1 '''downto''' 0 tmp.next = PersistentBinomialHeap(nodes[x]) tmp = tmp.next '''return''' (merge(H.next, H'.next), min.key)</code> Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Работает за Время работы операции <tex>O(\log n)</tex>.