73
правки
Изменения
Новая страница: «'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') - это приоритетная очеред...»
'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') - это приоритетная очередь, реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям.
== Основная идея ==
Возьмем [[Биномиальная куча|биномиальную кучу]] и реализуем ее на односвязных списках.
Для этого будем хранить список коней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, голова списка детей, но ребенок не будет знать родителя.
== Операции ==
=== Merge ===
Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.
<pre>
merge_tree(t1, t2)
if (t1.key < t2.key)
t2.next = t1.soon;
t1.soon = t2;
else
t1.next = t2.soon;
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>k</tex> и такое дерево одно. Добавим новое дерево ранга 0 - нашу вершину.
б) Минимальный ранг сына <tex>k</tex> и таких деревьев два. Объединим эти деревья и нашу вершину в дерево ранга <tex>k+1</tex>, получим дерево типа 1 или 2 в зависимости от того у какой вершины ключ меньше.
Тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
=== 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://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
== Основная идея ==
Возьмем [[Биномиальная куча|биномиальную кучу]] и реализуем ее на односвязных списках.
Для этого будем хранить список коней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, голова списка детей, но ребенок не будет знать родителя.
== Операции ==
=== Merge ===
Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.
<pre>
merge_tree(t1, t2)
if (t1.key < t2.key)
t2.next = t1.soon;
t1.soon = t2;
else
t1.next = t2.soon;
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>k</tex> и такое дерево одно. Добавим новое дерево ранга 0 - нашу вершину.
б) Минимальный ранг сына <tex>k</tex> и таких деревьев два. Объединим эти деревья и нашу вершину в дерево ранга <tex>k+1</tex>, получим дерево типа 1 или 2 в зависимости от того у какой вершины ключ меньше.
Тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
=== 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://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
