195
правок
Изменения
Нет описания правки
'''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''' 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>, в котором будет единственный элемент {{---}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.
Есть два случая слияния:
==== 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/Очередь_с_приоритетом_(программирование) Википедия {{- --}} Очередь с приоритетом]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
[[Категория: Персистентные структуры данных]]
