# [Перевод] Структуры данных на практике. Глава 12: Кучи и очереди с приоритетом
BotHabr (tgi,2) → All – 08:35:02 2026-04-19
Опубликовано: Sun, 19 Apr 2026 08:13:43 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их взаимосвязях», — Линус ТорвальдсСпоры о планировщикеНаша команда вела спор о структурах данных. Нам нужен был планировщик задач операционной системы реального времени, способный:Вставлять новые задачи с приоритетом (O(log n))Запрашивать задачу с наибольшим приоритетом (O(1))Удалять задачу с наибольшим приоритетом (O(log n))Кто-то предложил: «Давайте используем отсортированный массив». Но вставка будет занимать O(n) — придётся сдвигать элементы.Кто-то ещё сказал: «Возьмём связанный список». Однако поиск наибольшего выполняется за O(n) — необходимо сканировать весь список.Третий вспомнил о двоичном дереве поиска. Но из Главы 9 мы уже знаем, что BST ужасно ведут себя с кэшем.Споры продолжались, пока кто-то не упомянул двоичные кучи. Покончить с разногласиями позволили результаты бенчмарка Читать далее]]>
https://habr.com/ru/articles/1016636/
BotHabr (tgi,2) → All – 08:35:02 2026-04-19
Опубликовано: Sun, 19 Apr 2026 08:13:43 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их взаимосвязях», — Линус ТорвальдсСпоры о планировщикеНаша команда вела спор о структурах данных. Нам нужен был планировщик задач операционной системы реального времени, способный:Вставлять новые задачи с приоритетом (O(log n))Запрашивать задачу с наибольшим приоритетом (O(1))Удалять задачу с наибольшим приоритетом (O(log n))Кто-то предложил: «Давайте используем отсортированный массив». Но вставка будет занимать O(n) — придётся сдвигать элементы.Кто-то ещё сказал: «Возьмём связанный список». Однако поиск наибольшего выполняется за O(n) — необходимо сканировать весь список.Третий вспомнил о двоичном дереве поиска. Но из Главы 9 мы уже знаем, что BST ужасно ведут себя с кэшем.Споры продолжались, пока кто-то не упомянул двоичные кучи. Покончить с разногласиями позволили результаты бенчмарка Читать далее]]>
https://habr.com/ru/articles/1016636/