Изменения
Создана страница
'''''Куча Бродала-Окасаки''''' - основана на использовании персистентных приоритетных очередей. Поддерживает поиск минимума, вставку, слияние за <tex>O(1)</tex> в худшем случае и удаление минимума за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
== Структура ==
Используем структуру, которую Тарьян называет Bootstrapped. Она будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь Bootstrapped'опов упорядоченную по минимальному элементу. Это можно записать так:
<tex> BPQ<T_{min}, PQ> = (T_{min}, PQ<BPQ<T_{min}, PQ>>)</tex>
Куча из одного элемента будет выглядеть так
<tex>create(x) = BPQ<x, null></tex>
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру, где каждый элемент кучи будет храниться где-то в значений <tex>T_{min}</tex>.
== Операции ==
=== Merge ===
Слияние возможно выполнить за <tex>O(1)</tex> за счет того, что второй элемент пары это приоритетная очередь, элементами которой являются Bootstrapped.
<pre>
merge((x,q), (y,r))
if x<y
return (x, insert(q, (y,r)))
else
return (y, insert(r, (x,q)))
</pre>
Здесь <tex>insert</tex> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <tex>merge</tex> работает за <tex>O(1)</tex>.
=== Insert ===
Это создание нового Bootstrapped и <tex>merge</tex> его с основным деревом.
<pre>
insert((x,q), y)
return merge((x,q), create(y))
</pre>
Создание и <tex>merge</tex> выполняются за <tex>O(1)</tex>, тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
=== Find Min ===
Выполняется просто, так как Bootstrapped хранит минимум.
<pre>
findMin((x,q))
return x;
</pre>
=== Delete Min ===
Минимальный элемент хранится в верхнем Bootstrapped, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapped'пов.
<pre>
deleteMin((x,q))
((y,r), t) = extractMin(q)
return (y, merge(r, t))
</pre>
Здесь <tex>extractMin</tex> это извлечение минимума из приоритетной очереди, она вернет <tex>(y,r)</tex> {{---}} минимальный элемент типа Bootstrapped и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <tex>merge</tex> - слияние двух приоритетных очередей.
Возвращаем Bootstrapped, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.
Здесь <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>deleteMin</tex> выполняется за <tex>O(log N)</tex>.
== Смотри также ==
* [[Биномиальная куча]]
* [[Очередь]]
* [[Персистентная очередь]]
== Ссылки ==
[http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]
[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
== Структура ==
Используем структуру, которую Тарьян называет Bootstrapped. Она будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь Bootstrapped'опов упорядоченную по минимальному элементу. Это можно записать так:
<tex> BPQ<T_{min}, PQ> = (T_{min}, PQ<BPQ<T_{min}, PQ>>)</tex>
Куча из одного элемента будет выглядеть так
<tex>create(x) = BPQ<x, null></tex>
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру, где каждый элемент кучи будет храниться где-то в значений <tex>T_{min}</tex>.
== Операции ==
=== Merge ===
Слияние возможно выполнить за <tex>O(1)</tex> за счет того, что второй элемент пары это приоритетная очередь, элементами которой являются Bootstrapped.
<pre>
merge((x,q), (y,r))
if x<y
return (x, insert(q, (y,r)))
else
return (y, insert(r, (x,q)))
</pre>
Здесь <tex>insert</tex> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <tex>merge</tex> работает за <tex>O(1)</tex>.
=== Insert ===
Это создание нового Bootstrapped и <tex>merge</tex> его с основным деревом.
<pre>
insert((x,q), y)
return merge((x,q), create(y))
</pre>
Создание и <tex>merge</tex> выполняются за <tex>O(1)</tex>, тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
=== Find Min ===
Выполняется просто, так как Bootstrapped хранит минимум.
<pre>
findMin((x,q))
return x;
</pre>
=== Delete Min ===
Минимальный элемент хранится в верхнем Bootstrapped, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapped'пов.
<pre>
deleteMin((x,q))
((y,r), t) = extractMin(q)
return (y, merge(r, t))
</pre>
Здесь <tex>extractMin</tex> это извлечение минимума из приоритетной очереди, она вернет <tex>(y,r)</tex> {{---}} минимальный элемент типа Bootstrapped и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <tex>merge</tex> - слияние двух приоритетных очередей.
Возвращаем Bootstrapped, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.
Здесь <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>deleteMin</tex> выполняется за <tex>O(log N)</tex>.
== Смотри также ==
* [[Биномиальная куча]]
* [[Очередь]]
* [[Персистентная очередь]]
== Ссылки ==
[http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]
[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
