Изменения

'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') {{- это --}} [[Приоритетные очереди|приоритетная очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям.

== Наивная реализация Реализация с помощью дерева отрезов отрезков ==

Node(val : '''T''') <font color="darkgreen">//конструктор для листов</font> Node(leftChild : '''Node''', rightChild : '''Node''') <font color="darkgreen">//конструктор для узлов(присваивает полю key минимальное среди leftChild и rightChild)</font>

* <tex>\mathrm{build}</tex> {{--- }} построение дерева ,* <tex>\mathrm{insert}</tex> {{--- }} вставка нового элемента очереди,* <tex>\mathrm{extractMin}</tex> {{--- }} удаление минимального элемента очереди,* <tex>\mathrm{merge}</tex> {{--- }} слияние .

Вставлять новое значение мы будем в любой пустой лист. Лист считается пустым, если его значение равно <tex>\infty</tex>. При этом не стоит забывать, что те узлы, которые подвергаются изменению, нужно сначала скопировать, а потом вставить новый на основе скопированного для сохранения предыдущих состояний очереди. Запрос вставки нового ключа создает <tex>O(\log n)</tex> новых вершини время его работы <tex>O(n)</tex>.

'''return''' Node(currentNode.left, ytemp)

'''return''' Node(ytemp, currentNode.right)</code>

== Наивная = Недостатки реализации ===У данной реализации есть несколько существенных минусов:#Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных. #Вставка происходит за <tex>O(n)</tex>, что делает данную реализацию бесполезной на большом количестве данных. Такое же время работы можно было получить, если при каждом изменении [[Приоритетные очереди|приоритетной очереди]] просто копировать её и изменять.Более эффективной реализацией является персистентная приоритетная очередь построенная на [[Дерево поиска, наивная реализация |двоичном дереве поиска]]. Все операции, кроме слияния, выполняются за <tex>O(\log n)</tex>. К тому же [[Дерево поиска, наивная реализация|двоичное дерево поиска]] {{---}} динамическая структура, что позволит не думать об ограничении данных из-за реализации. == Реализация с помощью левосторонней кучи ==

Все операции практически (кроме <tex>\mathrm{merge}</tex>) аналогичны операциям с эфемерной [[Левосторонняя куча|левосторонней кучей]], только каждая из них возвращает корень измененной кучи. В частности <tex>\mathrm{extractMin}</tex> возвращает пару из извлеченной вершины и измененной кучи.

'''LeftistHeap''' merge(x: '''LeftistHeap''', y: '''LeftistHeap'''):

'''if''' y.key < >= x.key: swap z = LeftistHeap(x.left, merge(x.right, y), x.key) '''else''' z = LeftistHeap(xy.left, '''merge'''(xy.right, yx), xy.key)

== Основная идея Реализация с помощью биномиальной кучи ==

* <tex>key</tex> — {{---}} ключ (вес) элемента;,* <tex>next</tex> — {{---}} указатель на следующий элемент;,* <tex>child</tex> — {{---}} указатель на ребенка с большим рангом;,* <tex>degree</tex> — {{---}} степень узла (количество дочерних узлов данного узла).

Вспомогательная функция <tex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых {{- --}} новый корень, другой из них {{--- }} видоизмененный корень одного из деревьев.

tmp = PersistentBinomialHeap(t2) <font color = "green">//создаем новый узел путем копирования старого с помощью конструктора</font>

Общий принцип вставки нового элемента схож с принципом вставки в эфемерную обычную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</tex>, в котором будет единственный элемент {{- --}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.

а) #Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>. б) #Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент.ex>. Время работы <tex>O(\log n1)</tex>.

return mergeTreemerge(newRoot, heap)

===== Пример работы. Пусть дана куча: [[File:PersistentBinomialHeapExample1_3.png]] Вставим в кучу элемент, с ключом, равным 3. В данном случае выполняется условие под пунктом б). Тогда получим: [[File:PersistentBinomialHeapExample1_4.png]] Теперь вставим в эту же кучу элемент, с ключом, равным 4. Эта ситуация соответствует пункту а). Получим:=====

{| class = "wikitable" width="100%" ! Описание !! Изображение|-align="center"|Исходная куча.|[[File:PersistentBinomialHeapExample1_3.png]]|-align="center"|Вставим в кучу элемент, с ключом, равным <tex>3</tex>. В данном случае выполняется условие под пунктом <tex>2</tex>.|[[File:PersistentBinomialHeapExample1_4.png]]|-align="center"|Теперь вставим в эту же кучу элемент, с ключом, равным <tex>4</tex>. Эта ситуация соответствует пункту <tex>1</tex>. |[[File:PersistentBinomialHeapExample1_5.png]]|}

Работает так же как и в эфемерной обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. <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>.

*[http://ru.wikipedia.org/wiki/Очередь_с_приоритетом_(программирование) Википедия {{- --}} Очередь с приоритетом]