195
правок
Изменения
→insert
'''return''' ''null''
'''else'''
'''return''' Node(currentNode.left, ytemp)
'''else'''
'''return''' Node(ytemp, currentNode.right)</code>
==== extractMin ====
У данной реализации есть несколько существенных минусов:
#Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных.
#Вставка происходит за <tex>O(n)</tex>, что делает данную реализацию бесполезной на большом количестве данных. В этом случае Такое же время работы можно было получить, если при каждом изменении [[Приоритетные очереди |приоритетной очереди]] просто копировать её и изменять.
Более эффективной реализацией является персистентная приоритетная очередь построенная на [[Дерево поиска, наивная реализация|двоичном дереве поиска]]. Все операции, кроме слияния, выполняются за <tex>O(\log n)</tex>. К тому же [[Дерево поиска, наивная реализация|двоичное дерево поиска]] {{---}} динамическая структура, что позволит не думать об ограничении данных из-за реализации.
#Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.
#Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент. Время работы <tex>O(\log n1)</tex>.
Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.
newRoot = PersistentBinomialHeap(newVal)
'''if''' heap.degree == newRoot.degree:
return mergeTreemerge(newRoot, heap)
'''else'''
newRoot.next = heap
|[[File:PersistentBinomialHeapExample1_5.png]]
|}
==== extractMinimum ====
