Оглавление
Косая биномиальная куча
-
Косая биномиальная куча
- Структура данных для операций с приоритетными очередями
- Поддерживает операции вставки с постоянным временем
- Основана на косой двоичной системе счисления
-
Структура
- Лес косых биномиальных деревьев
- Косое биномиальное дерево ранга 0 — одноэлементный узел
- Простая ссылка связывает два дерева ранга r
- Косая связь типа А связывает три дерева
- Косая связь типа B связывает дерево ранга 0 и дерево ранга r
-
Операции
- Найти-минимум: O(log n) время
- Поглощать: O(log n) время
- Вставить: O(1) время
- Удалить-минимум: O(log n) время
- Клавиша уменьшения: O(log n) время
-
Оптимизация
- Бродал и Окасаки предложили технику “начальной загрузки”
- Временная сложность слияния снижена до O(1)
- Метод применим к любой приоритетной очереди с постоянной временной вставкой и логарифмическим объединением