Изменения

'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') {{- это --}} [[Приоритетные очереди|приоритетная очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям. == Реализация с помощью дерева отрезков == === Идея === Известно, что на основе [[Дерево отрезков. Построение|дерева отрезков]] можно построить полностью [[Персистентные структуры данных|персистентную структуру данных]]. Поэтому используем его, модифицируя операцию изменения на случай вставки и удаления элементов очереди. === Реализация === Будем хранить явные указатели на дочерние элементы. Тогда структура узла дерева примет следующий вид: <code> '''struct''' Node: '''Node''' left '''Node''' right '''T''' key Node(val : '''T''') <font color="darkgreen">// конструктор для листов</font> Node(leftChild : '''Node''', rightChild : '''Node''') <font color="darkgreen">// конструктор для узлов (присваивает полю key минимальное среди leftChild и rightChild)</font></code> Реализуем следующие функции:* <tex>\mathrm{build}</tex> {{---}} построение дерева,* <tex>\mathrm{insert}</tex> {{---}} вставка нового элемента очереди,* <tex>\mathrm{extractMin}</tex> {{---}} удаление минимального элемента очереди,* <tex>\mathrm{merge}</tex> {{---}} слияние. Каждая функция возвращает корень нового дерева, которое потом можно будет снова изменять. При реализации можно хранить отдельный массив корней деревьев и при каждом новом изменении какой-либо из версий добавлять измененную в конец массива. ==== build ==== Основная идея  Дерево будет построено фиксированного размера. Стоит отметить, что при создании нескольких деревьев необходимо придерживаться одного максимального размера. Асимптотика построения дерева отрезков составит <tex>O(n)</tex>. <code> '''Node''' build(left : '''uint''', right : '''uint'''): '''if''' left ==right '''return''' Node(<tex>\infty</tex>) '''uint''' mid =(left + right) / 2 '''return''' Node(build(left, mid), build(mid + 1, right))</code>  ==== insert ==== Вставлять новое значение мы будем в любой пустой лист. Лист считается пустым, если его значение равно <tex>\infty</tex>. При этом не стоит забывать, что те узлы, которые подвергаются изменению, нужно сначала скопировать, а потом вставить новый на основе скопированного для сохранения предыдущих состояний очереди. Запрос вставки нового ключа создает <tex>O(\log n)</tex> новых вершин и время его работы <tex>O(n)</tex>.  <code> '''Node''' insert(currentNode : '''Node''', newVal : '''T'''): '''if''' currentNode.left == ''null'' '''and''' currentNode.right == ''null'' '''and''' currentNode.val != <tex>\infty</tex> <font color="darkgreen">//если лист занят</font> '''return''' ''null'' '''if''' currentNode.left == ''null'' '''and''' currentNode.right == ''null'' '''and''' currentNode.val == <tex>\infty</tex> <font color="darkgreen">//если лист свободен</font> '''return''' Node(newVal) '''Node''' temp = insert(currentNode.left, newVal) '''if''' temp == ''null'' temp = insert(currentNode.right, newVal) '''if''' temp == ''null'' '''return''' ''null'' '''else''' '''return''' Node(currentNode.left, temp) '''else''' '''return''' Node(temp, currentNode.right)</code> ==== extractMin ==== Учитывая тот факт, что корень дерева содержит ключ минимального элемента, можно найти путь к листу, содержащему этот элемент, и удалить его. Аналогично вставке, не стоит забывать о сохранении предыдущих состояний очереди. Вызов функции должен производиться указанием в качестве аргументов корня дерева и значения в корне дерева. Запрос удаления минимального ключа создает <tex>O(\log n)</tex> новых вершин. <code> '''Node''' extractMin(currentNode : '''Node''', delVal : '''T'''): '''if''' currentNode.left == ''null'' '''and''' currentNode.right == ''null'' '''and''' currentNode.val == delVal '''return''' Node(<tex>\infty</tex>) '''if''' currentNode.left.val == delVal: '''return''' Node(extractMin(currentNode.left, delVal), currentNode.right) '''else''' '''return''' Node(currentNode.left, extractMin(currentNode.right, delVal))</code> ==== merge ==== Слияние двух деревьев будет производить с помощью конструктора структуры. Поэтому оно выполняется за <tex>O(1)</tex>.<code> '''Node''' merge(leftTree : '''Node''', rightTree : '''Node''') '''return''' Node(leftTree, rightTree)</code> === Недостатки реализации ===У данной реализации есть несколько существенных минусов:#Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных. #Вставка происходит за <tex>O(n)</tex>, что делает данную реализацию бесполезной на большом количестве данных. Такое же время работы можно было получить, если при каждом изменении [[Приоритетные очереди|приоритетной очереди]] просто копировать её и изменять.Более эффективной реализацией является персистентная приоритетная очередь построенная на [[Дерево поиска, наивная реализация|двоичном дереве поиска]]. Все операции, кроме слияния, выполняются за <tex>O(\log n)</tex>. К тому же [[Дерево поиска, наивная реализация|двоичное дерево поиска]] {{---}} динамическая структура, что позволит не думать об ограничении данных из-за реализации. == Реализация с помощью левосторонней кучи == Реализуем приоритетную очередь на [[Левосторонняя куча|левосторонней куче]]. Т.к. в [[Левосторонняя куча|левосторонней куче]] нигде не делается уничтожающих присваиваний, то можно её преобразовать в персистентную приоритетную очередь.  Будем хранить структуру:<code> '''struct''' LeftistHeap: '''LeftistHeap''' left '''LeftistHeap''' right '''T''' key '''int''' dist LeftistHeap(leftChild : '''LeftistHeap''', rightChild : '''LeftistHeap''', val : '''T''')</code> Приведём реализацию конструктора: <code> LeftistHeap(leftChild : '''LeftistHeap''', rightChild : '''LeftistHeap''', val : '''T'''): key = val '''if''' leftChild.dist > rightChild.dist left = leftChild right = rightChild '''else''' left = rightChild right = leftChild dist = min(left.dist, right.dist) + 1</code> === Поддерживаемые операции === Все операции практически (кроме <tex>\mathrm{merge}</tex>) аналогичны операциям с [[Левосторонняя куча|левосторонней кучей]], только каждая из них возвращает корень измененной кучи. В частности <tex>\mathrm{extractMin}</tex> возвращает пару из извлеченной вершины и измененной кучи. <tex>\mathrm{merge}</tex> примет следующий вид:<code> '''LeftistHeap''' merge(x : '''LeftistHeap''', y : '''LeftistHeap'''): '''if''' x == <tex> \varnothing </tex>: '''return''' y '''if''' y == <tex> \varnothing </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> == Реализация с помощью биномиальной кучи == 

Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя.Т.к. дочерний элемент не знает о своем родителе, то можно объединять деревья, сохраняя персистентность данной структуры.  === Структура кучи === Каждый узел в персистентной биномиальной куче представляется набором полей:* <tex>key</tex> {{---}} ключ (вес) элемента,* <tex>next</tex> {{---}} указатель на следующий элемент,* <tex>child</tex> {{---}} указатель на ребенка с большим рангом,* <tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).Доступ к куче осуществляется ссылкой на первый корень в списке корней.  === Операции === ==== getMinimum ==== Для нахождения минимального элемента необходимо пройти по списку корней дерева. Можно это сделать за <tex>O(\log n)</tex>, т.к. список корней содержит не более <tex>\log n</tex> элементов. На рисунке это корень второго дерева в куче.  [[File:PersistentBinomialHeapExample1_1.png]] ====merge = Merge === Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга. Вспомогательная функция <pretex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых {{---}} новый корень, другой из них {{---}} видоизмененный корень одного из деревьев.merge_tree<code> '''PersistentBinomialHeap''' mergeTree(t1: '''PersistentBinomialHeap''', t2: '''PersistentBinomialHeap'''): newRoot = PersistentBinomialHeap() tmp = PersistentBinomialHeap() newRoot.child = tmp newRoot.degree = t1.degree + t2.degree '''if ''' (t1.key < t2.key) tmp = PersistentBinomialHeap(t2) <font color = "green">// создаем новый узел путем копирования старого с помощью конструктора</font> tmp.next = t1.son;child newRoot.key = t1.soon = t2;key '''else''' tmp = PersistentBinomialHeap(t1) tmp.next = t2.son;child newRoot.key = t2.soon = key '''return''' newRoot</code> Процесс слияния двух деревьев показан на рисунке. Первоначально было два дерева <tex>t1;</pretex> и <tex>t2</tex>(на рисунке выделены черным). Затем их слили, появились два новых узла, которые обращаются по прежнему к старым поддеревьям (выделено красным). [[File:PersistentBinomialHeapExample1_2.png]]  Проход по корневым спискам выполнится за <tex>O(logN\log n)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>\mathrm{merge}</tex> работает за <tex>O(logN\log n)</tex>. ==== Insert insert ==== Общий принцип вставки нового элемента схож с принципом вставки в обычную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</tex>, в котором будет единственный элемент {{---}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.  Есть два случая слияния: Разрешим при объединении двух деревьев присоединять еще #Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну вершинус помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.#Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, дерево ранга 0в которую нужно добавить элемент. Время работы <tex>O(1)</tex>.  Тогда получится возможным существование еще двух типов деревьевамортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>. <code> '''PersistentBinomialHeap''' insert(heap : '''PersistentBinomialHeap''', newVal : '''T'''):[[Файл newRoot = PersistentBinomialHeap(newVal) '''if''' heap.degree == newRoot.degree:Persistent priority queue insert return merge(newRoot, heap) '''else''' newRoot.next = heap '''return''' newRoot</code> ===== Пример работы.png|300px]]=====

Разберем случаи добавления{| 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]]|}

б) Минимальный ранг дерева <tex>k</tex> Работает так же как и таких деревьев двав обычной [[Биномиальная куча|биномиальной куче]]. Объединим эти деревья Проходим по списку корней и нашу находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дерево дереве с минимальным ключом по возрастанию ранга . Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции <tex>k+1O(\log n)</tex>, получим дерево типа 1 или 2 в зависимости от того у какой вершины ключ меньше.

Тогда <tex>insert</tex> работает за <tex>O(1)</tex>== Cм.также ==

=== extractMinimum ===* [[Приоритетные очереди]]Работает так же как и в обычной * [[Биномиальная куча|биномиальной кучеПерсистентные структуры данных]]. Проходим по списку корней и находим вершину с минимальным ключом.<pre>extractMinimum(t) t1=t; while t1.next != null if min.val>t1.val min = t1; t1 = t1.next; par = t; t1 = t; while min != t1 par = t1; t1 = t1.next; par.next = par.next.next; return (min, t)</pre>Возвращает дерево с минимальным элементом и остаток от очереди после извлечения минимума. Работает за <tex>O(logN)</tex>.== Смотри также ==

* [[Левосторонняя куча]]* [[Персистентная очередь]] == Ссылки Источники информации == *[http://wwwcompscicenter.lektorium.tvru/courses/advanced-algo/2013-spring/classes/lecture723/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]*[http://logic.pdmi.ras.ru/csclub/node/2734 Лекция П.Ю. Мавривна по персистентным структурам данных]*[http://ru.wikipedia.org/wiki/Очередь_с_приоритетом_(программирование) Википедия {{---}} Очередь с приоритетом]