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

1.

Куча Бродала-Окасаки
От биномиальных куч к операциям с оптимальной
сложностью
Савранский Данила - 3385

2.

План построения из биномиальной кучи
1) Сократить сложность операции добавления элемента до
O(1), исключая возможность каскадного соединения
деревьев.
2) Сократить сложность нахождения минимума до O(1),
добавив глобальный минимум.
3) Сократить сложность слияния куч до O(1) путем
добавления возможности вложенности куч.

3.

Skew binary numbers
Это числа у которых k-ая цифра представляется как
и каждая цифра может быть 1 или 0 кроме первой
ненулевой цифры, которая может быть 2. Их преимущество
заключается в том, что при прибавлении 1 к числу,
возникает максимум один перенос, используя
. Прямо как биномиальная куча состоит из
биномиальных деревьев, skew binomial heap состоит из skew
binomial trees

4.

Skew binomial trees
Дерево 0-ого ранга - одна вершина. Дерево ранга r
получается соединением 2 деревьев ранга r - 1 одним из 3
способов:
a) Обычное соединение: такое же как и у биномиальных
деревьев
b) Соединение типа-A: 2 дерева ранга r - дети дерева ранга 0
c) Соединение типа-B: такое же как и у биномиальных, но к
основному корню слева добавляют ребенка дерево ранга
0

5.

Skew binomial heap
Это лес упорядоченных skew binomial деревьев, где нет двух деревьев с одинаковым рангом, за
исключением, возможно, двух деревьев с наименьшим рангом.
Операция нахождения минимума такая же как у биномиальной кучи.
Операция добавления элемента O(1) - создаем дерево 0 ранга из элемента, и смотрим на 2 первых
по рангу дерева в куче, если ранги одинаковы то выполняем соединение типа A или B, в
зависимости от того, какой корень окажется минимальным. Если они разных рангов то просто
добавляем дерево в кучу.
Слияние - Исключаем повторяющиеся деревья в каждой кучи путем обычного соединения, затем
соединяем кучи как биномиальные.
Удаление минимального элемента - после удаление элемента оставшиеся дети ранга > 0 образуют
кучу. Принимаем операцию слияния между оригинальной и новой кучей, а затем добавляем все
оставшиеся деревья ранга 0

6.

Добавляем глобальный минимум
Чтобы снизить поиск минимума до O(1) создадим структуру
пары <глобальный минимум, куча>.
1) Поиск минимума - возвращает глобальный минимум
O(1)
2) Добавление элемента - зависит от кучи, при
необходимости меняем глобальный минимум и
добавляем его
3) Слияние - зависит от кучи, после слияния добавляем
наибольший глобальный минимум в кучу
4) Удаление минимума - зависит от кучи, удаляем
минимум и ставим его как новый глобальный минимум

7.

Bootstrapping
Создаем кучу, элементами которой будут являться такие же кучи, хранить нужные
значения будем путем хранения кучи как пары, как из прошлого пункта. Куча из одного
элемента определяется как <x, null>. Каждая операция вложенной кучи может быть
определена реализацией самой кучи.
1)
2)
3)
4)
Поиск минимума - возвращает глобальный минимум
Слияние - добавляем кучу с большим минимумом как элемент другой кучи.
(Использует добавление из реализации кучи)
Добавление элемента - создаем кучу <x, null> и используем слияние из прошлого
пункта. (Использует добавление из реализации кучи)
Удаление минимума - находим минимальный элемент из вложенной кучи <y, q1>, удаляем минимальный элемент получаем q2 и сливаем q1 и q2 в одну кучу,
получая вложенную кучу <y, merge(q1, q2)> (Использует нахождение минимума,
удаление минимума и слияние из реализации кучи)

8.

Bootstrapping
Теперь рассмотрим сложность операций:
1) Поиск минимума - не зависит от реализации кучи O(1)
2) Слияние - использует добавление из реализации кучи,
для skew binomial heap это O(1)
3) Добавление - тоже самое, что и слияние O(1)
4) Удаление минимума - Использует нахождение
минимума, удаление минимума и слияние из
реализации кучи, для skew binomial heap все эти
операции представлены за O(log(N)), значит итоговая
сложность будет O(log(N))

9.

Заключение
Мы рассмотрели структуру Бродала-Окасаки — приоритетную очередь, которая
сохраняет асимптотику биномиальной кучи для удаления минимума (O(logn), но при
этом улучшает асимптотику следующих операций: поиск минимума, добавление
элемента, слияние куч на O(1).
Однако, несмотря на теоретическую оптимальность, эта структура редко
применяется на практике. Сам Герд Бродал отмечал, что сложность реализации и
высокие константы делают ее менее эффективной в реальных задачах, чем другие
структуры — даже с худшей асимптотикой.

10.

Использованные источники
Brodal, Okasaki. Optimal Purely Functional Priority Queues (1996)
Brodal queue - en Wikipedia