Изменения

'''Персистентная приоритетная очередь''' (англ. ''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> == Реализация с помощью биномиальной кучи == 

Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя.== Операции ===== Merge ===Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.<pre>merge_tree(t1, t2) if (t1.key < t2.key) t2.next = t1.son; t1.soon = t2; else t1.next = t2Т.son; t2к.soon = t1;</pre>Проход по корневым спискам выполнится за <tex>O(logN)</tex>дочерний элемент не знает о своем родителе, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>merge</tex> работает за <tex>O(logN)</tex>.=== Insert ===Разрешим при объединении двух деревьев присоединять еще одну вершинуто можно объединять деревья, дерево ранга 0. Тогда получится возможным существование еще двух типов деревьев:[[Файл:Persistent priority queue insertсохраняя персистентность данной структуры.png|300px]]

аКаждый узел в персистентной биномиальной куче представляется набором полей:* <tex>key</tex> {{---}} ключ (вес) Минимальный ранг дерева элемента,* <tex>knext</tex> и такое дерево одно{{---}} указатель на следующий элемент,* <tex>child</tex> {{---}} указатель на ребенка с большим рангом,* <tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла). Добавим новое дерево ранга 0 - нашу вершинуДоступ к куче осуществляется ссылкой на первый корень в списке корней.

==== getMinimum ==== Для нахождения минимального элемента необходимо пройти по списку корней дерева. Можно это сделать за <tex>O(\log n)</tex>, т.к. список корней содержит не более <tex>\log n</tex> элементов. На рисунке это корень второго дерева в куче.  [[File:PersistentBinomialHeapExample1_1.png]] ==== merge ==== Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.  Вспомогательная функция <tex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых {{---}} новый корень, другой из них {{---}} видоизмененный корень одного из деревьев.<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.child newRoot.key = t1.key '''else''' tmp = PersistentBinomialHeap(t1) tmp.next = t2.child newRoot.key = t2.key '''return''' newRoot</code> Процесс слияния двух деревьев показан на рисунке. Первоначально было два дерева <tex>t1</tex> и <tex>t2</tex> (на рисунке выделены черным). Затем их слили, появились два новых узла, которые обращаются по прежнему к старым поддеревьям (выделено красным). [[File:PersistentBinomialHeapExample1_2.png]]  Проход по корневым спискам выполнится за <tex>O(\log n)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>insert\mathrm{merge}</tex> работает за <tex>O(1\log n)</tex>. ====insert = extractMinimum ===Работает так же как и Общий принцип вставки нового элемента схож с принципом вставки в обычной обычную [[Биномиальная куча|биномиальной кучебиномиальную кучу]]. Проходим по списку корней и находим вершину Создаем кучу с минимальным ключомдеревом ранга <tex>0</tex>, в котором будет единственный элемент {{---}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.  Есть два случая слияния: #Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <pretex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.extractMinimum#Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент. Время работы <tex>O(t1)</tex>. t1=t; while t1Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.next ! <code> '''PersistentBinomialHeap''' insert(heap : '''PersistentBinomialHeap''', newVal : '''T'''): newRoot = nullPersistentBinomialHeap(newVal) '''if min''' heap.val>t1degree == newRoot.valdegree: min return merge(newRoot, heap) '''else''' newRoot.next = t1;heap '''return''' newRoot</code>  t1 = t1==== Пример работы.next;=====  par {| class = t; t1 "wikitable" width= t;"100%" while min != t1Описание !! Изображение par |-align= t1;"center" t1 = t1|Исходная куча.next; par|[[File:PersistentBinomialHeapExample1_3.next png]]|-align= par"center"|Вставим в кучу элемент, с ключом, равным <tex>3</tex>.nextВ данном случае выполняется условие под пунктом <tex>2</tex>.|[[File:PersistentBinomialHeapExample1_4.next;png]]|-align="center" return (min|Теперь вставим в эту же кучу элемент, с ключом, t)равным <tex>4</tex>. Эта ситуация соответствует пункту <tex>1</pretex>. |[[File:PersistentBinomialHeapExample1_5.png]]|}Возвращает ==== extractMinimum ==== Работает так же как и в обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево , которое хранит минимальный ключ. Сортируем детей в дереве с минимальным элементом ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и остаток от очереди новую кучу после извлечения минимума. Работает за Время работы операции <tex>O(logN\log n)</tex>. == Смотри Cм. также == * [[Приоритетные очереди]]* [[Персистентные структуры данных]]

* [[Левосторонняя куча]]* [[Персистентная очередь]] == Ссылки Источники информации == *[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/Очередь_с_приоритетом_(программирование) Википедия {{---}} Очередь с приоритетом]