Куча (Heap) — это область в оперативной памяти, используемая для динамического распределения памяти во время выполнения программы.
Основные особенности:
- Память выделяется и освобождается явно программистом (или сборщиком мусора).
- Нет строгой последовательности выделения/освобождения блоков памяти.
- Управление памятью сложнее, чем в стеке, может привести к фрагментации и утечкам памяти.
Виды куч (в контексте структур данных):
- Бинарная куча (Binary Heap): Дерево, удовлетворяющее свойству кучи. Для любой ноды (кроме корня) ее значение либо меньше, либо больше значения родителя.
- Min Heap: Значение родителя всегда меньше или равно значениям потомков. Минимальный элемент находится в корне.
- Max Heap: Значение родителя всегда больше или равно значениям потомков. Максимальный элемент находится в корне.
- Двоичная куча (Binomial Heap): Коллекция биномиальных деревьев, удовлетворяющих определенным свойствам. Поддерживает эффективные операции слияния.
- Фибоначчиева куча (Fibonacci Heap): Структура данных, используемая в алгоритмах, таких как алгоритм Дейкстры. Обеспечивает более эффективные амортизированные временные сложности для некоторых операций по сравнению с бинарной кучей.
- Спаренные кучи (Pairing Heap): Простая в реализации структура данных с хорошими амортизированными временными сложностями.
- Левосторонняя куча (Leftist Heap): Структура данных, облегчающая эффективное слияние. Важным свойством является "ранг", или "нулевая длина пути", который используется для быстрого объединения.
Эти виды куч используются в различных алгоритмах, таких как сортировка (Heap Sort), реализация приоритетных очередей, алгоритмы поиска кратчайшего пути и др. Выбор конкретного вида кучи зависит от требуемых операций и их временной эффективности.