Викиконспекты - Вклад участника [ru]

Куча Бродала-Окасаки

2013-06-11T08:51:06Z

94.25.229.57: /* getMin */

'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, что позволяет делать <tex>insert</tex> за <tex>O(1)</tex>, добавлении минимального элемента, позволяет получать минимальный элемент за <tex>O(1)</tex>, и идеи Data-structural bootstrapping, позволяющей выполнить <tex>merge</tex> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

== Структура ==
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.
{{Определение
|neat = 0
|definition= Data-structural bootstrapping - это идея, позволяющая снизить время <tex>merge</tex> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
}}

Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:

<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>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ.
<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 ===
Это создание нового BPQ и <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>.
=== getMin ===
Выполняется просто, так как BPQ хранит минимум.
<pre>
getMin((x,q))
return x;
</pre>
Очевидно, работает за <tex>O(1)</tex>

=== extractMin ===
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.
<pre>
extractMin((x,q))
((y,r), t) = extractMin(q)
return (y, merge(r, t))
</pre>
Здесь <tex>extractMin(q)</tex> {{---}} это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает <tex>(y,r)</tex> - минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума - <tex>t</tex>. <tex>merge</tex> {{---}} функция, выполняющая слияние двух приоритетных очередей.

Возвращаем BPQ, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.

Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>extractMin</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]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]

Куча Бродала-Окасаки

2013-06-11T08:49:32Z

94.25.229.57:

'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, что позволяет делать <tex>insert</tex> за <tex>O(1)</tex>, добавлении минимального элемента, позволяет получать минимальный элемент за <tex>O(1)</tex>, и идеи Data-structural bootstrapping, позволяющей выполнить <tex>merge</tex> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

== Структура ==
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.
{{Определение
|neat = 0
|definition= Data-structural bootstrapping - это идея, позволяющая снизить время <tex>merge</tex> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
}}

Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:

<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>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ.
<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 ===
Это создание нового BPQ и <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>.
=== getMin ===
Выполняется просто, так как Bootstrapping хранит минимум.
<pre>
getMin((x,q))
return x;
</pre>
Очевидно, работает за <tex>O(1)</tex>

=== extractMin ===
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.
<pre>
extractMin((x,q))
((y,r), t) = extractMin(q)
return (y, merge(r, t))
</pre>
Здесь <tex>extractMin(q)</tex> {{---}} это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает <tex>(y,r)</tex> - минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума - <tex>t</tex>. <tex>merge</tex> {{---}} функция, выполняющая слияние двух приоритетных очередей.

Возвращаем BPQ, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.

Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>extractMin</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]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]

Куча Бродала-Окасаки

2013-06-11T08:43:08Z

94.25.229.57:

'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и идеи Data-structural bootstrapping. Поддерживает поиск минимума, вставку, слияние за <tex>O(1)</tex> в худшем случае и удаление минимума за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

== Структура ==
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.
{{Определение
|neat = 0
|definition= Data-structural bootstrapping - это идея, позволяющая снизить время <tex>merge</tex> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
}}

Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:

<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>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ.
<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 ===
Это создание нового BPQ и <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>.
=== getMin ===
Выполняется просто, так как Bootstrapping хранит минимум.
<pre>
getMin((x,q))
return x;
</pre>
Очевидно, работает за <tex>O(1)</tex>

=== extractMin ===
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.
<pre>
extractMin((x,q))
((y,r), t) = extractMin(q)
return (y, merge(r, t))
</pre>
Здесь <tex>extractMin(q)</tex> {{---}} это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает <tex>(y,r)</tex> - минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума - <tex>t</tex>. <tex>merge</tex> {{---}} функция, выполняющая слияние двух приоритетных очередей.

Возвращаем BPQ, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.

Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>extractMin</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]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]