Куча Бродала-Окасаки — различия между версиями
(Создана страница) |
|||
Строка 10: | Строка 10: | ||
<tex>create(x) = BPQ<x, null></tex> | <tex>create(x) = BPQ<x, null></tex> | ||
− | Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру, где | + | Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру, где каждое значение будет храниться где-то в одном из значений <tex>T_{min}</tex>. |
== Операции == | == Операции == |
Версия 01:39, 8 июня 2013
Куча Бродала-Окасаки - основана на использовании персистентных приоритетных очередей. Поддерживает поиск минимума, вставку, слияние за
в худшем случае и удаление минимума за в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.Содержание
Структура
Используем структуру, которую Тарьян называет Bootstrapped. Она будет хранить пару из минимального элемента
и приоритетную очередь Bootstrapped'опов упорядоченную по минимальному элементу. Это можно записать так:
Куча из одного элемента будет выглядеть так
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру, где каждое значение будет храниться где-то в одном из значений
.Операции
Merge
Слияние возможно выполнить за
за счет того, что второй элемент пары это приоритетная очередь, элементами которой являются Bootstrapped.merge((x,q), (y,r)) if x<y return (x, insert(q, (y,r))) else return (y, insert(r, (x,q)))
Здесь
это добавление в приоритетную очередь работает за , тогда работает за .Insert
Это создание нового Bootstrapped и
его с основным деревом.insert((x,q), y) return merge((x,q), create(y))
Создание и
выполняются за , тогда работает за .Find Min
Выполняется просто, так как Bootstrapped хранит минимум.
findMin((x,q)) return x;
Delete Min
Минимальный элемент хранится в верхнем Bootstrapped, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapped'пов.
deleteMin((x,q)) ((y,r), t) = extractMin(q) return (y, merge(r, t))
Здесь
это извлечение минимума из приоритетной очереди, она вернет — минимальный элемент типа Bootstrapped и остаток от приоритетной очереди после извлечение минимума — . - слияние двух приоритетных очередей.Возвращаем Bootstrapped, где
— новый минимальный элемент, и приоритетная очередь без элемента .Здесь
и выполняются за , тогда выполняется за .