195
правок
Изменения
Нет описания правки
'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') {{- это --}} [[Приоритетные очереди|приоритетная очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям.
== Реализация с помощью дерева отрезков ==
Реализуем следующие функции:
* <tex>\mathrm{build}</tex> {{--- }} построение дерева ,* <tex>\mathrm{insert}</tex> {{--- }} вставка нового элемента очереди,* <tex>\mathrm{extractMin}</tex> {{--- }} удаление минимального элемента очереди,* <tex>\mathrm{merge}</tex> {{--- }} слияние .
Каждая функция возвращает корень нового дерева, которое потом можно будет снова изменять. При реализации можно хранить отдельный массив корней деревьев и при каждом новом изменении какой-либо из версий добавлять измененную в конец массива.
==== insert ====
Вставлять новое значение мы будем в любой пустой лист. Лист считается пустым, если его значение равно <tex>\infty</tex>. При этом не стоит забывать, что те узлы, которые подвергаются изменению, нужно сначала скопировать, а потом вставить новый на основе скопированного для сохранения предыдущих состояний очереди. Запрос вставки нового ключа создает <tex>O(\log n)</tex> новых вершини время его работы <tex>O(n)</tex>.
<code>
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: swap z = LeftistHeap(x.left, '''merge'''(x.right, y), x.key) '''else''' z = LeftistHeap(xy.left, '''merge'''(xy.right, yx), xy.key)
'''return''' z
</code>
== Основная идея Реализация с помощью биномиальной кучи ==
Возьмем [[Биномиальная куча|биномиальную кучу]] и реализуем ее на односвязных списках.
Каждый узел в персистентной биномиальной куче представляется набором полей:
* <tex>key</tex> — {{---}} ключ (вес) элемента;,* <tex>next</tex> — {{---}} указатель на следующий элемент;,* <tex>child</tex> — {{---}} указатель на ребенка с большим рангом;,* <tex>degree</tex> — {{---}} степень узла (количество дочерних узлов данного узла).
Доступ к куче осуществляется ссылкой на первый корень в списке корней.
Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.
Вспомогательная функция <tex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых {{- --}} новый корень, другой из них {{--- }} видоизмененный корень одного из деревьев.
<code>
'''PersistentBinomialHeap''' mergeTree(t1 : '''PersistentBinomialHeap''', t2 : '''PersistentBinomialHeap'''):
==== insert ====
Общий принцип вставки нового элемента схож с принципом вставки в эфемерную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</tex>, в котором будет единственный элемент {{- --}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.
Есть два случая слияния:
Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.
</code>
===== Пример работы. Пусть дана куча: [[File:PersistentBinomialHeapExample1_3.png]] Вставим в кучу элемент, с ключом, равным 3. В данном случае выполняется условие под пунктом б). Тогда получим: [[File:PersistentBinomialHeapExample1_4.png]] Теперь вставим в эту же кучу элемент, с ключом, равным 4. Эта ситуация соответствует пункту а). Получим: [[File:PersistentBinomialHeapExample1_5.png]]=====
{| 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]]
|}
==== extractMinimum ====
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
