Алгоритмы с нуля
Heap: тест с выбором ответа
Суть Тест с выбором ответа на синтез по всему юниту: инвариант heap, O(n) build-heap, контракт priority queue и выбор нужного heap для top-k и k-way merge.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов, проходящих через весь юнит. Ни один не на заучивание определений — каждый это проектное решение: какой heap, какая сложность, какой инвариант. Выберите ответ, который защитили бы на собеседовании, затем прочитайте, почему каждый отвлекающий вариант ошибочен.
Цель
Убедитесь, что можете связать инвариант heap, аргумент O(n) для build-heap, контракт priority queue и приём «heap размера k», на котором строятся и top-k, и k-way merge — синтез, к которому вели пять уроков.
Викторина
Completed
Интервьюер даёт массив [10, 5, 20, 15, 30] и спрашивает: «это корректный min-heap?» Каков верный ответ и почему?
Heads-up Неотсортированность не критерий. В heap для каждого узла должно выполняться «родитель ≤ оба ребёнка». Здесь 10 > 5 в корне, значит проверка не пройдена — независимо от сортировки.
Heads-up Min-heap это НЕ отсортированный массив. [1, 3, 2, 5, 4] корректный min-heap, но не отсортирован. Достаточно лишь отношения «родитель–ребёнок» на каждом индексе.
Heads-up Присутствия минимума мало; в min-heap минимум должен быть в корне (индекс 0). Здесь корень 10, а не 5.
Викторина
Completed
Построение heap из массива n элементов через n вызовов push даёт O(n log n), но стандартный build-heap (heapify) — O(n). Откуда ускорение?
Heads-up build-heap делает sift-down для каждого нелистового узла — около n/2 узлов. Узлы не пропускаются; выигрыш в том, что узлы у дна (большинство) имеют крошечную высоту поддерева, и каждый sift-down дёшев.
Heads-up build-heap доказуемо O(n). Сумма Σ (n/2^{h+1})·h сходится к константе, умноженной на n, поэтому heapify линеен — стандартный, хорошо известный результат.
Heads-up build-heap есть O(n) на ЛЮБОМ входе, отсортированном или нет. Граница идёт из распределения высот узлов, которое не зависит от значений.
Викторина
Completed
Коллега говорит: «priority queue — это просто heap». Почему это неточно и когда различие реально важно?
Heads-up Оно влияет на реальные решения. У обычного binary heap нет эффективного decrease-key, поэтому для Dijkstra на плотных графах нужна другая реализация PQ. Именно отделение контракта от реализации позволяет её заменить.
Heads-up У ADT нет собственной скорости — скорость даёт реализация. PQ на отсортированном массиве имеет insert за O(n); на heap — за O(log n). ADT это контракт, а не утверждение о производительности.
Heads-up peek за O(1) — как раз свойство, которое реализация heap даёт контракту PQ. ADT PQ задаёт peek; heap делает его O(1).
Викторина
Completed
Нужно держать k наибольших элементов из потока n чисел (k ≪ n). Какой heap и почему именно он, а не другой?
Heads-up Для k НАИБОЛЬШИХ нужно вытеснять НАИМЕНЬШЕГО кандидата при переполнении. Max-heap скрывает минимум, поэтому поиск вытесняемого стоит O(k). Min-heap держит вытесняемого в корне — в этом весь приём.
Heads-up Это O(n + k log n) времени и O(n) памяти — вы сохранили всё. Min-heap размера k даёт O(n log k) времени и O(k) памяти, что и нужно при k ≪ n и потоке, который нельзя удержать целиком.
Heads-up Выбор меняет стоимость вытеснения с O(log k) (min-heap, вытесняемый в корне) на O(k) (max-heap, нужно сканировать минимум). Это решение о корректной сложности, а не стиль.
Викторина
Completed
В k-way merge из k отсортированных списков с n элементами всего каждая запись в heap хранит (value, listIndex, position), а не только значение. Зачем эта учётная информация?
Heads-up Длина списка не важна для merge. Учётная информация нужна, чтобы при удалении головы заменить её следующим элементом именно этого списка — сохраняя ровно по одному кандидату от каждого активного списка.
Heads-up Дубликаты сливаются и без дополнительных метаданных. Задача метаданных — продвижение: знать, из какого списка взять преемника после каждого извлечения.
Heads-up Граница O(n log k) идёт из того, что heap держит не более k элементов, поэтому каждый pop/push есть O(log k). Метаданные нужны для корректности (продвижения нужного списка), а не для границы сложности.
Викторина
Completed
При pop из min-heap последний элемент массива переносится в корень, массив уменьшается на один, затем делается sift-down. Почему поднимают ПОСЛЕДНИЙ элемент, а не продвигают меньшего ребёнка в образовавшуюся дыру?
Heads-up У последнего элемента нет особого ранга — это просто крайний правый лист. Его берут, потому что его удаление сохраняет форму полного дерева, затем sift-down чинит порядок. Обычно он крупный, поэтому и опускается обратно.
Heads-up Продвижение детей не запрещено библиотекой; его избегают, потому что оно может нарушить инвариант формы полного бинарного дерева, на котором держится индексная арифметика массива.
Heads-up Только перенос последнего элемента сохраняет форму полного дерева, которая нужна представлению массивом (без внутренних дыр). Продвижение детей может создать дыру не в конце, ломая индексные формулы.
Итог
Сквозная линия юнита — одна структура, выполняющая много ролей. Свойство heap плюс форма полного дерева дают peek за O(1) и push/pop за O(log n) через sift-up и sift-down; build-heap использует распределение высот и достигает O(n). Оберните это в контракт priority queue — и та же машина становится планировщиком, фильтром top-k (min-heap размера k, вытесняем корень) и k-way merge (по одному кандидату от списка, продвигаем по listIndex). Каждый вопрос здесь был по сути про «какой инвариант или какой heap» — ровно то решение, что вы принимаете на собеседовании или в реальной системе.