195
правок
Изменения
→insert
'''Node''' right
'''T''' key
Node(val : '''T''') <font color="darkgreen">//конструктор для листов</font> Node(leftChild : '''Node''', rightChild : '''Node''') <font color="darkgreen">//конструктор для узлов(присваивает полю key минимальное среди leftChild и rightChild)</font>
</code>
'''return''' ''null''
'''else'''
'''return''' Node(currentNode.left, ytemp)
'''else'''
'''return''' Node(ytemp, currentNode.right)</code>
==== extractMin ====
'''return''' Node(leftTree, rightTree)
</code>
=== Недостатки реализации ===
У данной реализации есть несколько существенных минусов:
#Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных.
#Вставка происходит за <tex>O(n)</tex>, что делает данную реализацию бесполезной на большом количестве данных. Такое же время работы можно было получить, если при каждом изменении [[Приоритетные очереди|приоритетной очереди]] просто копировать её и изменять.
Более эффективной реализацией является персистентная приоритетная очередь построенная на [[Дерево поиска, наивная реализация|двоичном дереве поиска]]. Все операции, кроме слияния, выполняются за <tex>O(\log n)</tex>. К тому же [[Дерево поиска, наивная реализация|двоичное дерево поиска]] {{---}} динамическая структура, что позволит не думать об ограничении данных из-за реализации.
== Реализация с помощью левосторонней кучи ==
'''return''' x
'''if''' y.key >= x.key:
z = LeftistHeap(x.left, '''merge'''(x.right, y), x.key)
'''else'''
z = LeftistHeap(y.left, '''merge'''(y.right, x), y.key)
'''return''' z
</code>
newRoot.degree = t1.degree + t2.degree
'''if''' (t1.key < t2.key)
tmp = PersistentBinomialHeap(t2) <font color = "green">//создаем новый узел путем копирования старого с помощью конструктора</font>
tmp.next = t1.child
newRoot.key = t1.key
==== insert ====
Общий принцип вставки нового элемента схож с принципом вставки в эфемерную обычную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</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 ====
Работает так же как и в эфемерной обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции <tex>O(\log n)</tex>.
== Cм. также ==
*[http://compscicenter.ru/courses/advanced-algo/2013-spring/classes/723/ Лекция А.С. Станкевича по приоритетным очередям]
*[http://logic.pdmi.ras.ru/csclub/node/2734 Лекция П.Ю. Мавривна по персистентным структурам данных]
*[http://ru.wikipedia.org/wiki/Очередь_с_приоритетом_(программирование) Википедия {{- --}} Очередь с приоритетом]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
[[Категория: Персистентные структуры данных]]
