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

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

Структура

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

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

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

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

[math] BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)[/math]

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

[math] \mathrm{create} [/math][math](x) = BPQ \left \langle x, null\right \rangle[/math]

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

Операции

Merge

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

BPQ merge([math] \langle [/math]x : int, q : BPQ[math] \rangle [/math], [math] \langle [/math]y:int, r:bpq[math] \rangle [/math]:pair):
    if x < y
        return (x, insert(q, [math] \langle [/math]y, r[math] \rangle [/math]))
    else
        return (y, insert(r, [math] \langle [/math]x, q[math] \rangle [/math]))

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

Insert

Это создание нового [math] BPQ [/math] и [math]\mathrm{merge}[/math] его с основным деревом.

[math] \langle [/math]int, bpq[math] \rangle [/math] insert([math] \langle [/math]x:int, q:bpq[math] \rangle [/math], y:bpq):
    return merge([math] \langle [/math]x, q[math] \rangle [/math], create(y))

Создание и [math]\mathrm{merge}[/math] выполняются за [math]O(1)[/math], тогда [math]\mathrm{insert}[/math] работает за [math]O(1)[/math].

getMin

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

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

Очевидно, работает за [math]O(1)[/math].

extractMin

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

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

Здесь [math]\mathrm{extractMin}[/math]— это функция, извлекающая минимальный элемент типа [math] BPQ [/math] из приоритетной очереди, она возвращает [math](y,r)[/math] — минимальный элемент типа [math] BPQ [/math] и остаток от приоритетной очереди после извлечение минимума — [math]t[/math]. [math]\mathrm{merge}[/math] функция, выполняющая слияние двух приоритетных очередей.

Возвращаем [math] BPQ [/math], где [math]y[/math] — новый минимальный элемент, и [math]\mathrm{merge}[/math] приоритетная очередь без элемента [math]y[/math].

Так как [math]\mathrm{extractMin}[/math] и [math]\mathrm{merge}[/math] выполняются за [math]O(\log N)[/math], тогда [math]\mathrm{extractMin}[/math] выполняется за [math]O(\log N)[/math].

Смотри также

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

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

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

• Optimal Purely Functional Priority Queues