Бродал очередь — Arc.Ask3.Ru

Очередь Бродаля Очередь Бродала Структура очереди с кучей/приоритетом   Низкие временные рамки в наихудшем случае: O(1) для вставки, O(log(n)) для удаления   […]

Очередь Бродаля

  • Очередь Бродала

    • Структура очереди с кучей/приоритетом  
    • Низкие временные рамки в наихудшем случае: O(1) для вставки, O(log(n)) для удаления  
    • Названа в честь Герта Стелтинга Бродала  
  • Сложность и применимость

    • Лучшие асимптотические оценки среди приоритетных очередей  
    • Сложны и неприменимы на практике  
    • Бродал и Окасаки предложили постоянную версию очередей Бродала  
  • Временные сложности

    • Различные структуры данных кучи имеют разные временные сложности  
    • Аббревиатура am. указывает на амортизированную сложность  
    • Названия операций предполагают минимальное количество операций  
  • Рекомендации

    • Герт Столтинг Бродал (1996) «Эффективные приоритетные очереди в наихудшем случае»  
    • Герт Столтинг Бродал и Крис Окасаки (1996) «Оптимальные чисто функциональные очереди с приоритетами»  

Полный текст статьи:

Бродал очередь — Arc.Ask3.Ru

Оставьте комментарий

Прокрутить вверх