Очередь Бродаля
-
Очередь Бродала
- Структура очереди с кучей/приоритетом
- Низкие временные рамки в наихудшем случае: O(1) для вставки, O(log(n)) для удаления
- Названа в честь Герта Стелтинга Бродала
-
Сложность и применимость
- Лучшие асимптотические оценки среди приоритетных очередей
- Сложны и неприменимы на практике
- Бродал и Окасаки предложили постоянную версию очередей Бродала
-
Временные сложности
- Различные структуры данных кучи имеют разные временные сложности
- Аббревиатура am. указывает на амортизированную сложность
- Названия операций предполагают минимальное количество операций
-
Рекомендации
- Герт Столтинг Бродал (1996) «Эффективные приоритетные очереди в наихудшем случае»
- Герт Столтинг Бродал и Крис Окасаки (1996) «Оптимальные чисто функциональные очереди с приоритетами»