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

Куча Бродала-Окасаки (англ. 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]:

BPQ = <int, PQ(BPQ)> 

Куча из одного элемента создается так:

BPQ singleton'(x:int):
    return <x, null>

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

Операции

Merge

Слияние выполняется выбором минимума из двух значений [math]T_{min}[/math]. Этот элемент и станет вершиной кучи. Это позволит в любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции [math]\mathrm{insert}[/math].

BPQ merge(<x:int, q:PQ>, <y:int, r:PQ>):
    if x < y
        return <x, insert(q, <y, r>)>
    else
        return <y, insert(r, <x, q>)>

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

Insert

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

BPQ insert(<x:int, q:PQ>, y:int):
    return merge(<x, q>, singleton(y))

По сути операция [math]\mathrm{insert}[/math] - тот же самый [math]\mathrm{merge}[/math]: создается дерево нулевого ранга за [math]O(1)[/math], а затем оно сливается с основным также за [math]O(1)[/math].

getMin

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

int getMin(<x:int, q:PQ>):
    return x

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

extractMin

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

<int, BPQ> extractMin(<x:int, q:PQ>):
    <<y, r>, t> = extractMin(q)
    return <x, <y, merge(r, t)>>

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

Возвращаем минимум и [math] BPQ [/math], где [math]x[/math] — новый минимальный элемент, и [math]\mathrm{merge}(r,t)[/math] — приоритетная очередь без элементов [math]x[/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].

Смотри также

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

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

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

• Optimal Purely Functional Priority Queues