Изменения

'''Персистентная приоритетная очередь''' (англ. ''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> новых вершин.  <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, y) '''else''' '''return''' Node(y, 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> == Наивная реализация с помощью левосторонней кучи == Реализуем приоритетную очередь на [[Левосторонняя куча|левосторонней куче]]. Т.к. в [[Левосторонняя куча|левосторонней куче]] нигде не делается уничтожающих присваиваний, то можно её преобразовать в персистентную приоритетную очередь.  Будем хранить структуру:<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, y): '''if''' x == <tex> \varnothing </tex>: '''return''' y '''if''' y == <tex> \varnothing </tex>: '''return''' x '''if''' y.key < x.key: swap(x, y) z = LeftistHeap(x.left, '''merge'''(x.right, y), x.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 === Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.  Вспомогательная функция <tex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых - новый корень, другой из них - видоизмененный корень одного из деревьев.<precode>merge_tree '''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.son = t2;key '''else''' tmp = PersistentBinomialHeap(t1) tmp.next = t2.son;child newRoot.key = t2.son = t1;key</pre> '''return''' newRootПроход по корневым спискам выполнится за <tex>O(logN)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>merge</tex> работает за <tex>O(logN)</texcode>.

=== Insert ===Разрешим при объединении Процесс слияния двух деревьев присоединять еще одну вершинупоказан на рисунке. Первоначально было два дерева <tex>t1</tex> и <tex>t2</tex> (на рисунке выделены черным). Затем их слили, появились два новых узла, дерево ранга 0. Тогда получится возможным существование еще двух типов деревьев:[[Файл:Persistent priority queue insertкоторые обращаются по прежнему к старым поддеревьям (выделено красным).png|300px]]

Так же разрешим хранить два дерева одинакового ранга[[File:PersistentBinomialHeapExample1_2.png]]

Разберем случаи добавленияПроход по корневым спискам выполнится за <tex>O(\log n)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>\mathrm{merge}</tex> работает за <tex>O(\log n)</tex>.

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

Есть два случая слияния: а) Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>. б) Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент.ex>. Время работы <tex>O(\log n)</tex>. Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex> работает . <code> '''PersistentBinomialHeap''' insert(heap : '''PersistentBinomialHeap''', newVal : '''T'''): newRoot = PersistentBinomialHeap(newVal) '''if''' heap.degree == newRoot.degree: return mergeTree(newRoot, heap) '''else''' newRoot.next = heap '''return''' newRoot</code> Пример работы. Пусть дана куча: [[File:PersistentBinomialHeapExample1_3.png]] Вставим в кучу элемент, с ключом, равным 3. В данном случае выполняется условие под пунктом б). Тогда получим: [[File:PersistentBinomialHeapExample1_4.png]] Теперь вставим в эту же кучу элемент, с ключом, равным 4. Эта ситуация соответствует пункту а). Получим: [[File:PersistentBinomialHeapExample1_5.png]] ==== extractMinimum ==== Работает так же как и в эфемерной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. <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(1\log n)</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/Очередь_с_приоритетом_(программирование) Википедия - Очередь с приоритетом]