Куча Бродала-Окасаки — различия между версиями
Kris (обсуждение | вклад) (→extractMinimum) |
Kris (обсуждение | вклад) (→getMinimum) |
||
Строка 41: | Строка 41: | ||
</pre> | </pre> | ||
Создание и <tex>merge</tex> выполняются за <tex>O(1)</tex>, тогда <tex>insert</tex> работает за <tex>O(1)</tex>. | Создание и <tex>merge</tex> выполняются за <tex>O(1)</tex>, тогда <tex>insert</tex> работает за <tex>O(1)</tex>. | ||
− | === | + | === getMin === |
Выполняется просто, так как Bootstrapping хранит минимум. | Выполняется просто, так как Bootstrapping хранит минимум. | ||
<pre> | <pre> | ||
− | + | getMin((x,q)) | |
return x; | return x; | ||
</pre> | </pre> | ||
+ | |||
=== extractMin === | === extractMin === | ||
Минимальный элемент хранится в верхнем Bootstrapping, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapping'ов. | Минимальный элемент хранится в верхнем Bootstrapping, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapping'ов. |
Версия 05:12, 11 июня 2013
Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) - основана на использовании персистентных приоритетных очередей. Поддерживает поиск минимума, вставку, слияние за в худшем случае и удаление минимума за в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
Содержание
Структура
Структура
Используем технику, которую Тарьян называет data-structural bootstrapping.
Она будет хранить пару из минимального элемента
и приоритетную очередь Bootstrapping'ов упорядоченную по минимальному элементу. Это можно записать так:
Куча из одного элемента будет выглядеть так
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений
.Операции
Merge
Слияние выполняется выбором минимума из двух значений
и добавлением в приоритетную очередь второго Bootstrapping.merge((x,q), (y,r)) if x<y return (x, insert(q, (y,r))) else return (y, insert(r, (x,q)))
Здесь
это добавление в приоритетную очередь работает за , тогда работает за .Insert
Это создание нового Bootstrapping и
его с основным деревом.insert((x,q), y) return merge((x,q), create(y))
Создание и
выполняются за , тогда работает за .getMin
Выполняется просто, так как Bootstrapping хранит минимум.
getMin((x,q)) return x;
extractMin
Минимальный элемент хранится в верхнем Bootstrapping, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapping'ов.
extractMin((x,q)) ((y,r), t) = extractMin(q) return (y, merge(r, t))
Здесь
— это функция, извлекающая - минимальный элемент типа Bootstrapping - из приоритетной очереди, она возвращает - минимальный элемент типа Bootstrapping и остаток от приоритетной очереди после извлечение минимума - . — функция, выполняющая слияние двух приоритетных очередей.Возвращаем Bootstrapping, где
— новый минимальный элемент, и приоритетная очередь без элемента .Так как
и выполняются за , тогда выполняется за .