Куча (heap) — это специальная структура данных, которая позволяет быстро получать элемент с максимальным или минимальным приоритетом. Чаще всего используется двоичная куча: почти полное бинарное дерево, обычно хранящееся в массиве.
- Max-heap: каждый родитель больше или равен детям
- Min-heap: каждый родитель меньше или равен детям
Из-за такой структуры корень всегда содержит самый “важный” элемент. Именно поэтому куча — стандартная основа для приоритетной очереди.
Где применяются кучи
💡 На практике heap используют в задачах, где нужно постоянно брать лучший элемент:
- планировщики задач в ОС
- алгоритмы поиска кратчайшего пути, например Dijkstra
- обработка событий
- top-K элементов
- слияние отсортированных потоков данных
Почему куча удобна
Основные операции работают быстро:
- получение максимума/минимума — O(1)
- вставка элемента — O(log n)
- удаление корня — O(log n)
- построение кучи из массива — O(n)
Это делает heap эффективнее обычного массива, если приоритеты часто меняются.
Как работает приоритетная очередь
При добавлении новый элемент ставится в конец массива, а затем “всплывает” вверх, пока не восстановится свойство кучи.
При удалении корня:
- корень заменяют последним элементом
- последний элемент удаляют
- новый корень “просеивают” вниз
Так поддерживается правильный порядок без полной сортировки всего набора.
Что такое heapsort
Heapsort — это алгоритм сортировки на основе кучи 🧠
Как он работает:
- сначала из массива строится max-heap
- затем максимальный элемент перемещается в конец
- размер кучи уменьшается
- оставшаяся часть снова восстанавливается в heap
В итоге массив сортируется по возрастанию.
Сложность heapsort
- лучшее время — O(n log n)
- среднее время — O(n log n)
- худшее время — O(n log n)
- дополнительная память — O(1)
Это важное преимущество: heapsort не требует дополнительного массива, в отличие от mergesort.
Плюсы heapsort
- ✅ гарантированное O(n log n)
- ✅ сортировка in-place
- ✅ не боится худшего сценария, как quicksort
Минусы heapsort
- ⚠️ хуже кэш-локальность, чем у quicksort
- ⚠️ на практике часто медленнее быстрой сортировки
- ⚠️ heap не сохраняет относительный порядок равных элементов, то есть сортировка нестабильная
Когда использовать
Heap полезен, если нужен не просто отсортированный массив, а именно:
- быстрый доступ к минимальному/максимальному элементу
- частые вставки и удаления по приоритету
- обработка данных в реальном времени
А heapsort стоит выбирать, когда важны:
- предсказуемая производительность
- минимум дополнительной памяти
- отсутствие провалов в худшем случае 🚀
Подборку каналов про IT — от алгоритмов до архитектуры и карьеры — стоит сохранить отдельно 👀