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

Куча Бродала-Окасаки - основана на использовании персистентных приоритетных очередей. Поддерживает поиск минимума, вставку, слияние за [math]O(1)[/math] в худшем случае и удаление минимума за [math]O(log N)[/math] в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

Структура

Используем структуру, которую Тарьян называет Bootstrapped. Она будет хранить пару из минимального элемента [math]T_{min}[/math] и приоритетную очередь Bootstrapped'опов упорядоченную по минимальному элементу. Это можно записать так:

[math] BPQ\lt T_{min}, PQ\gt = (T_{min}, PQ\lt BPQ\lt T_{min}, PQ\gt \gt )[/math]

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

[math]create(x) = BPQ\lt x, null\gt [/math]

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

Операции

Merge

Слияние возможно выполнить за [math]O(1)[/math] за счет того, что второй элемент пары это приоритетная очередь, элементами которой являются Bootstrapped.

merge((x,q), (y,r))
  if x<y
    return (x, insert(q, (y,r)))
  else
    return (y, insert(r, (x,q)))

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

Insert

Это создание нового Bootstrapped и [math]merge[/math] его с основным деревом.

insert((x,q), y)
  return merge((x,q), create(y))

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

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))

Здесь [math]extractMin[/math] это извлечение минимума из приоритетной очереди, она вернет [math](y,r)[/math] — минимальный элемент типа Bootstrapped и остаток от приоритетной очереди после извлечение минимума — [math]t[/math]. [math]merge[/math] - слияние двух приоритетных очередей.

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

Здесь [math]extractMin[/math] и [math]merge[/math] выполняются за [math]O(log N)[/math], тогда [math]deleteMin[/math] выполняется за [math]O(log N)[/math].

Смотри также

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

Ссылки

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

Optimal Purely Functional Priority Queues