Что такое куча и приоритетная очередь?
Деревья и кучи
Куча — полное бинарное дерево, хранимое в массиве, с порядком «родитель не больше детей» (min-heap); приоритетная очередь на ней даёт вставку и извлечение минимума за O(log n).
Представление в массиве
- Дети узла i — индексы 2i+1 и 2i+2, родитель — (i−1)/2.
- Полнота дерева достигается плотным заполнением массива без дыр.
Операции
push: добавить элемент в конец и «просеять вверх» — O(log n).pop: забрать корень, перенести последний элемент в корень и «просеять вниз» — O(log n).heapifyпроизвольного массива — O(n), что быстрее n отдельных вставок.
Применения
- Приоритетные очереди: планировщики, алгоритм Дейкстры, k наибольших элементов, слияние k отсортированных списков.
- Heapsort: O(n log n) in-place, но нестабильная сортировка.
Чего куча не умеет
Поиск произвольного элемента — O(n): порядок частичный, куча «знает» только про корень.
Коротко для собеседования
Куча — массив, в котором корень всегда минимален, поэтому добавить элемент или достать минимум стоит O(log n), а построение из готового массива — O(n). Её берут, когда постоянно нужен «самый важный» элемент, как в Дейкстре или top-k; max-heap получается инверсией компаратора, а поиск произвольного элемента в куче медленный.