Куча

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

История

Понятие кучи как структуры данных было впервые формализовано в 1964 году британским учёным в области информатики Тони Хоаром, который также известен как создатель алгоритма быстрой сортировки. Однако своё современное название и широкое распространение куча получила благодаря работе Роберта Флойда и Джона Уильямса, которые в 1964 году разработали алгоритм пирамидальной сортировки (heapsort). Именно Уильямс ввёл термин «heap» (куча) для описания этой структуры. В последующие десятилетия кучи стали одним из базовых элементов теории алгоритмов и структур данных, изучаемых в курсах информатики во всём мире.

Классификация

Кучи классифицируют по нескольким признакам, основным из которых является тип упорядочения элементов.

По типу упорядочения

• Макс-куча (max-heap): Для любого узла значение ключа родителя больше или равно значениям ключей его потомков. Наибольший элемент всегда находится в корне дерева.
• Мин-куча (min-heap): Для любого узла значение ключа родителя меньше или равно значениям ключей его потомков. Наименьший элемент всегда находится в корне дерева.

По структуре дерева

• Двоичная куча (binary heap): Наиболее распространённая реализация, в которой куча представляется в виде полного бинарного дерева. Все уровни дерева, кроме, возможно, последнего, полностью заполнены, а последний уровень заполняется слева направо. Двоичные кучи обычно реализуются на основе массива.
• Биномиальная куча (binomial heap): Представляет собой набор биномиальных деревьев, каждое из которых удовлетворяет свойству кучи. Биномиальные кучи поддерживают эффективное слияние двух куч, что делает их полезными для реализации объединяемых приоритетных очередей.
• Куча Фибоначчи (Fibonacci heap): Более сложная структура, представляющая собой набор деревьев, удовлетворяющих свойству кучи. Отличается от биномиальной кучи тем, что деревья не обязательно являются биномиальными. Куча Фибоначчи обеспечивает очень быструю асимптотику для операций вставки, слияния и уменьшения ключа, что делает её особенно эффективной в алгоритмах, где эти операции выполняются часто (например, в алгоритме Дейкстры).
• Куча-лес (pairing heap): Простая в реализации структура, которая на практике часто не уступает кучам Фибоначчи, хотя её теоретическая асимптотика хуже.

Устройство и характеристики

Основная идея кучи заключается в поддержании частичного порядка среди элементов. В отличие от полностью упорядоченных структур, таких как двоичное дерево поиска, куча гарантирует только то, что корень содержит экстремальный элемент (максимальный или минимальный). Это позволяет выполнять операции вставки и извлечения экстремума за логарифмическое время.

Операции

Над кучей определены следующие основные операции:

• Вставка (insert): Добавление нового элемента в кучу. Элемент помещается в конец массива (на последний уровень дерева), а затем «всплывает» (процедура sift-up или heapify-up) до тех пор, пока не будет восстановлено свойство кучи. Время выполнения: O(log n).
• Извлечение максимума/минимума (extract-max/extract-min): Удаление корневого элемента (максимального или минимального). На его место помещается последний элемент массива, который затем «опускается» (процедура sift-down или heapify-down) до восстановления свойства кучи. Время выполнения: O(log n).
• Просмотр корня (peek): Получение значения корневого элемента без его удаления. Время выполнения: O(1).
• Слияние (merge): Объединение двух куч в одну. Для двоичных куч эта операция может быть выполнена путём последовательной вставки элементов одной кучи в другую, что даёт сложность O(n). Биномиальные кучи и кучи Фибоначчи поддерживают слияние за O(log n) и O(1) соответственно.
• Уменьшение/увеличение ключа (decrease-key/increase-key): Изменение приоритета элемента на новый. После изменения элемент «всплывает» или «опускается» для восстановления свойства кучи. Эта операция критически важна для алгоритмов на графах, таких как алгоритм Дейкстры.

Реализация на массиве

Двоичная куча часто реализуется с помощью массива, что позволяет эффективно использовать кэш-память процессора. Для элемента с индексом i (индексация обычно начинается с 0 или 1) его потомки находятся по индексам 2i+1 и 2i+2 (при индексации с 0), а родитель — по индексу (i-1)/2 (целочисленное деление).

Применение

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

Пирамидальная сортировка (Heapsort)

Один из классических алгоритмов сортировки, использующий макс-кучу. Сначала из исходного массива строится куча, а затем многократно извлекается корневой элемент (максимальный), который помещается в конец отсортированной части массива. Сложность алгоритма — O(n log n) в худшем, среднем и лучшем случаях.

Приоритетные очереди

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

Алгоритмы на графах

• Алгоритм Дейкстры: Использует мин-кучу для эффективного поиска вершины с наименьшим расстоянием на каждом шаге. Куча Фибоначчи позволяет достичь наилучшей теоретической сложности этого алгоритма.
• Алгоритм Прима: Применяется для построения минимального остовного дерева графа. Также использует мин-кучу для выбора ребра с наименьшим весом.

Управление памятью

В системах программирования термин «куча» (heap) также используется для обозначения области динамической памяти, из которой выделяются блоки для объектов и структур данных. Хотя эта область не обязательно реализована как структура данных «куча», её название исторически связано с тем, что выделение и освобождение памяти в ней часто управляется с помощью приоритетных очередей или структур, напоминающих кучу. В частности, сборщики мусора в языках программирования (например, Java, C#) могут использовать кучи для отслеживания доступных блоков памяти.

Медианная фильтрация

В обработке сигналов и изображений кучи используются для реализации медианных фильтров, которые позволяют удалять шум, сохраняя края объектов. Фильтр скользящего окна может быть эффективно реализован с помощью двух куч (макс-кучи и мин-кучи), поддерживающих текущую медиану.

Примеры

Пример на псевдокоде (макс-куча)

``` // Вставка элемента function insert(heap, value): heap.append(value) i = heap.length - 1 while i > 0 and heap[parent(i)] < heap[i]: swap(heap[parent(i)], heap[i]) i = parent(i)

// Извлечение максимума function extractMax(heap): max = heap[0] heap[0] = heap[heap.length - 1] heap.pop() siftDown(heap, 0) return max

// Процедура опускания function siftDown(heap, i): largest = i left = 2i + 1 right = 2i + 2 if left < heap.length and heap[left] > heap[largest]: largest = left if right < heap.length and heap[right] > heap[largest]: largest = right if largest != i: swap(heap[i], heap[largest]) siftDown(heap, largest) ```

Интересные факты

• Алгоритм пирамидальной сортировки, использующий кучу, является одним из немногих алгоритмов сортировки, который сочетает в себе гарантированную сложность O(n log n) и отсутствие потребности в дополнительной памяти (сортировка на месте).
• Термин «куча» в контексте структуры данных не имеет прямого отношения к куче мусора (garbage-collected heap) в языках программирования, хотя оба понятия связаны с управлением памятью.
• В русскоязычной литературе по информатике структура «куча» часто называется «пирамидой», что отражает её иерархическую природу.

Критика

Несмотря на свою эффективность, кучи имеют ряд ограничений. Основным недостатком является невозможность быстрого поиска произвольного элемента. Если требуется найти элемент по значению, а не по приоритету, куча не предоставляет эффективных средств для этого (поиск занимает O(n)). Кроме того, двоичные кучи не поддерживают эффективное слияние, что ограничивает их применение в задачах, где требуется объединение нескольких приоритетных очередей. Для таких случаев разработаны более сложные структуры, такие как биномиальные кучи и кучи Фибоначчи.

Источники

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Седжвик, Р., Уэйн, К. Алгоритмы на Java. — 4-е изд. — М.: Вильямс, 2016.
• Кнут, Д. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2007.
• Williams, J. W. J. Algorithm 232: Heapsort. Communications of the ACM, 1964.