куча

Статьи

SRT Алгоритм Пирамидальная сортировка Куча прямо в массиве: n log n в худшем случае без лишней памяти — страховка introsort и сортировка ядра Linux. O(n log n) 2 задачи SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи GRA Алгоритм A* Дейкстра с подсказкой «сколько ещё до финиша»: волна тянется к цели, а путь остаётся кратчайшим. O((V + E) log V) 2 задачи GRA Алгоритм Двунаправленный поиск Две волны Дейкстры навстречу друг другу: где остановиться, сколько экономится и как подружить с A*. O((V + E) log V) 2 задачи GRA Алгоритм Иерархии сжатия Предподсчёт навигаторов: сжимаем неважные перекрёстки в ярлыки и ищем путь двумя волнами вверх. O((V + E′) log V) 1 задача GRA Алгоритм Минимальное остовное дерево Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму. O(E log V) 2 задачи STR Алгоритм Код Хаффмана Оптимальный префиксный код по частотам знаков: два самых редких дерева склеиваются, пока не останется одно. O(n log n) 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача SYS Алгоритм Резервуарная выборка k случайных элементов из потока неизвестной длины за один проход и O(k) памяти. O(n) 2 задачи SYS Алгоритм Планирование задач Порядок работы: короткие сначала, сроки, прерывания, много ядер и аномалии Грэма. O(n log n): сортировка или куча 2 задачи TEC Приём Как выбрать структуру данных Сначала список операций, потом структура: стоимость каждой операции в Python и Go на одной карте. зависит от выбора 1 задача

Задачи

Выборка по энергии Заехать по пути Заказы по сроку Лучшие абзацы Маршрут курьера Самые частые слова Сейсмическая тревога Сколько бит займёт текст Сколько нужно залов Сколько сэкономил Флойд Хроника из региональных каталогов Ближайшие города Водопад загрузки Где может лежать k-й Заправки по пути Запросы по ярусам Кратчайший остаток Медиана за окно Один бесплатный проезд Пожарные части Сколько успеть к сроку Нумерация глав Пятнашки за наименьшее число ходов

Часто рядом

собеседования 10 классика 9 в проде 8 жадность 5 взвешенный граф 5 граф 5 карты и навигация 5 дерево 4 кратчайший путь 4 массив 3 операционные системы 3 расписание 3