Куча Бродала-Окасаки
Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) — основана на использовании биномиальной кучи без каскадных ссылок, что позволяет делать за , добавлении минимального элемента, позволяет получать минимальный элемент за , и идеи Data-structural bootstrapping, позволяющей выполнить за . Удаление минимума работает за в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
Содержание
Структура
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента
и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по . Это можно записать так:
Куча из одного элемента будет выглядеть так
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений
.Операции
Merge
Слияние выполняется выбором минимума из двух значений
pair merge((x : int, q : bpq) : pair, (y : int, r : bpq) : pair) if x < y return (x, insert(q, (y, r))) else return (y, insert(r, (x, q)))
Здесь
это добавление в приоритетную очередь работает за , тогда работает за .Insert
Это создание нового BPQ и
pair(int, bpq) insert((x : int, q : bpq), y : bpq) return merge((x,q), create(y))
Создание и
выполняются за , тогда работает за .getMin
Выполняется просто, так как BPQ хранит минимум.
getMin((x,q)) return x;
Очевидно, работает за
extractMin
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.
extractMin((x,q)) ((y,r), t) = extractMin(q) return (y, merge(r, t))
Здесь
— это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает — минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума — . — функция, выполняющая слияние двух приоритетных очередей.Возвращаем BPQ, где
— новый минимальный элемент, и приоритетная очередь без элемента .Так как
и выполняются за , тогда выполняется за .