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

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

Структура

Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.

Определение:

Data-structural bootstrapping — это идея, позволяющая снизить время $\mathrm{merge}$ до $O(1)$ путем разрешения хранить в очереди другую очередь.

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

$BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)$

Куча из одного элемента будет выглядеть так

$\mathrm{create}$$(x) = BPQ \left \langle x, null\right \rangle$

Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений $T_{min}$.

Операции

Merge

Слияние выполняется выбором минимума из двух значений $T_{min}$ и добавлением в приоритетную очередь второго BPQ.

pair(int, bpq) 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)))

Здесь $\mathrm{insert}$ это добавление в приоритетную очередь работает за $O(1)$, тогда $\mathrm{merge}$ работает за $O(1)$.

Insert

Это создание нового BPQ и $merge$ его с основным деревом.

pair(int, bpq) insert((x : int, q : bpq), y : bpq)
    return merge((x,q), create(y))

Создание и $merge$ выполняются за $O(1)$, тогда $insert$ работает за $O(1)$.

getMin

Выполняется просто, так как BPQ хранит минимум.

int getMin((x : int, q : bpq))
    return x;

Очевидно, работает за $O(1)$

extractMin

Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.

pair (int, bpq) extractMin(pair(x : int, q : bpq))
    ((y,r), t) = extractMin(q)
return (y, merge(r, t))

Здесь $extractMin(q)$ — это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает $(y,r)$ — минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума — $t$. $merge$ — функция, выполняющая слияние двух приоритетных очередей.

Возвращаем BPQ, где $y$ — новый минимальный элемент, и $merge(r, t)$ приоритетная очередь без элемента $y$.

Так как $extractMin$ и $merge$ выполняются за $O(\log N)$, тогда $extractMin$ выполняется за $O(\log N)$.

Смотри также

• Биномиальная куча
• Очередь
• Персистентная очередь
• Персистентная приоритетная очередь

Источники информации

• Лекция А.С. Станкевича по приоритетным очередям

• Optimal Purely Functional Priority Queues