Стек, очередь и куча

Стек и его секретное оружие

Стек живёт по правилу «последним вошёл - первым вышел» и появляется везде, где что-то надо отложить и потом вернуться: проверка скобок, отмена действий, стек вызовов функций, обход в глубину. Скобки - канонический пример: открывающие складываем, на каждой закрывающей вершина обязана совпасть по типу, в конце стек должен опустеть.

Секретное оружие - монотонный стек, то есть стек, в котором значения намеренно держатся возрастающими или убывающими. Он решает за один проход целый класс задач «найди ближайший больший элемент справа».

Пройдём по температурам [3, 1, 4, 2], задача - через сколько дней станет теплее. Кладём в стек индексы. День 0 (3 градуса): стек пуст, кладём. День 1 (1 градус): вершина - тройка, она больше единицы, не трогаем, кладём. День 2 (4 градуса): единица меньше четвёрки - снимаем, для того дня ответ 2 − 1 = 1; тройка тоже меньше - снимаем, ответ 2 − 0 = 2; кладём. День 3 (2 градуса): вершина - четвёрка, больше двойки, просто кладём. В стеке остались дни без ответа, им ноль. Итог [2, 1, 0, 0].

// Почему это O(n), хотя внутри есть вложенный while: каждый индекс кладётся в стек ровно один раз и снимается не больше одного раза. Всего действий не больше 2n, независимо от того, как они распределились по шагам.

монотонный стек

стек, в котором поддерживается порядок значений. Нарушители выталкиваются, и в момент выталкивания как раз и находится ответ для них

Очередь: порядок поступления

Очередь работает по правилу «первым вошёл - первым вышел» и обрабатывает элементы в порядке прихода: обход графа в ширину, разбор дерева по уровням, буферы задач.

Есть классическая проверка на понимание: подмени в обходе в ширину очередь на стек, и он молча превратится в обход в глубину. Код останется рабочим, ошибки не будет, но обход перестанет идти по уровням, и кратчайшие пути сломаются - потому что кратчайший путь в невзвешенном графе гарантирован именно порядком уровней.

Deque - двусторонняя очередь, у которой обе операции на обоих концах стоят O(1). Нужна там, где приходится и добавлять, и выбрасывать с разных сторон: скользящий максимум в окне, история действий с ограниченной глубиной.

// Разминочный вопрос, который до сих пор задают: как сделать очередь из двух стеков. Ответ - один стек на вход, второй на выход; когда выходной пуст, всё содержимое входного переливается в него, разворачиваясь. Амортизированно O(1), потому что каждый элемент переливается ровно один раз.

Куча: экстремум, а не порядок

Куча - это двоичное дерево, у которого выполнено ровно одно условие: родитель не больше любого из своих детей (для кучи на минимум). Никаких требований к порядку между братьями нет.

Хранится она обычным массивом, без единой ссылки: дети элемента с индексом i лежат на позициях 2i+1 и 2i+2. Дерево получается сбалансированным по построению, поэтому его высота - log n, и отсюда сразу цена операций: вставка и снятие минимума стоят O(log n), потому что каждая из них поднимает или опускает один элемент вдоль пути от корня к листу.

Куча отвечает ровно на один вопрос - «дай минимум за O(log n), не сортируя всё остальное». На этом стоят топ-k, слияние k отсортированных списков, планировщики задач и медиана потока двумя кучами: в одной левая половина чисел максимумом вверх, в другой правая минимумом вверх, медиана всегда на стыке.

// Куча НЕ отсортирована, и это главный источник ошибок. Гарантия есть только у корня, а порядок соблюдается лишь вдоль путей от корня к листьям. Пройтись по массиву кучи подряд - совсем не то же самое, что перебрать элементы по возрастанию; полный порядок получается только последовательным выниманием. Ещё две неожиданности: построить кучу из готового массива можно за O(n), а не за O(n log n), зато найти в куче произвольный элемент стоит O(n) - она для экстремума, не для поиска.

приоритетная очередь

абстракция «выдай самый приоритетный элемент». Куча - её стандартная реализация, поэтому эти два слова часто употребляют как синонимы

Как отвечать: «Найди топ-10 самых частых слов в большом файле»

Сначала один проход по файлу со словарём частот. Дальше не сортирую весь словарь, а держу кучу на минимум размера десять: кладу туда пары «частота и слово», и как только размер переваливает за десять, снимаю минимум. В куче всегда остаётся текущая десятка, а наверху - кандидат на вылет. Получается O(n log 10), практически линейно, против O(n log n) у полной сортировки. Если файл не влезает в память, считаю частоты по кускам и сливаю их внешним слиянием, либо беру приближённые счётчики вроде count-min sketch, когда точность не критична. В Python heapq - это именно куча на минимум, что для задачи про топ-частые как раз удобно.

Паттерн «куча размера k», честно посчитанная сложность и заранее взятый поворот на «а если не влезает в память». Три уровня глубины вместо одного, и последний интервьюер обычно и хочет услышать.

На чём валят

• −Считать, что обход массива кучи подряд даёт элементы по возрастанию: порядок есть только вдоль путей корень-лист.
• −Искать произвольный элемент в куче: это O(n), куча приспособлена только к экстремуму.
• −Подменить очередь стеком в обходе в ширину: код работает, но это уже обход в глубину, и кратчайшие пути сломаны.
• −Забыть, что heapq в Python - только куча на минимум; для максимума кладут отрицательные значения или кортежи со знаком.
• −Сортировать весь массив ради топ-k, когда куча размера k делает то же дешевле.