Куча Бродала-Окасаки — различия между версиями
Строка 1: | Строка 1: | ||
− | '''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и | + | '''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и идеи Data-structural bootstrapping. Поддерживает поиск минимума, вставку, слияние за <tex>O(1)</tex> в худшем случае и удаление минимума за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей. |
== Структура == | == Структура == | ||
− | Используем | + | Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. |
{{Определение | {{Определение | ||
|neat = 0 | |neat = 0 | ||
− | |definition= | + | |definition= Data-structural bootstrapping - это идея, позволяющая снизить время <tex>merge</tex> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь. |
}} | }} | ||
Строка 25: | Строка 25: | ||
== Операции == | == Операции == | ||
=== Merge === | === Merge === | ||
− | Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго | + | Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ. |
<pre> | <pre> | ||
merge((x,q), (y,r)) | merge((x,q), (y,r)) | ||
Строка 35: | Строка 35: | ||
Здесь <tex>insert</tex> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <tex>merge</tex> работает за <tex>O(1)</tex>. | Здесь <tex>insert</tex> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <tex>merge</tex> работает за <tex>O(1)</tex>. | ||
=== Insert === | === Insert === | ||
− | Это создание нового | + | Это создание нового BPQ и <tex>merge</tex> его с основным деревом. |
<pre> | <pre> | ||
insert((x,q), y) | insert((x,q), y) | ||
Строка 50: | Строка 50: | ||
=== extractMin === | === extractMin === | ||
− | Минимальный элемент хранится в верхнем | + | Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов. |
<pre> | <pre> | ||
extractMin((x,q)) | extractMin((x,q)) | ||
Строка 56: | Строка 56: | ||
return (y, merge(r, t)) | return (y, merge(r, t)) | ||
</pre> | </pre> | ||
− | Здесь <tex>extractMin(q)</tex> {{---}} это функция, извлекающая минимальный элемент типа | + | Здесь <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>. | Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>extractMin</tex> выполняется за <tex>O(log N)</tex>. |
Версия 11:43, 11 июня 2013
Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) - основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и идеи Data-structural bootstrapping. Поддерживает поиск минимума, вставку, слияние за в худшем случае и удаление минимума за в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
Содержание
Структура
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента
и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по . Это можно записать так:
Куча из одного элемента будет выглядеть так
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений
.Операции
Merge
Слияние выполняется выбором минимума из двух значений
и добавлением в приоритетную очередь второго BPQ.merge((x,q), (y,r)) if x<y return (x, insert(q, (y,r))) else return (y, insert(r, (x,q)))
Здесь
это добавление в приоритетную очередь работает за , тогда работает за .Insert
Это создание нового BPQ и
его с основным деревом.insert((x,q), y) return merge((x,q), create(y))
Создание и
выполняются за , тогда работает за .getMin
Выполняется просто, так как Bootstrapping хранит минимум.
getMin((x,q)) return x;
Очевидно, работает за
extractMin
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.
extractMin((x,q)) ((y,r), t) = extractMin(q) return (y, merge(r, t))
Здесь
— это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает - минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума - . — функция, выполняющая слияние двух приоритетных очередей.Возвращаем BPQ, где
— новый минимальный элемент, и приоритетная очередь без элемента .Так как
и выполняются за , тогда выполняется за .