Куча (структура данных)

Эта статья — о структуре данных в программировании. О динамической области распределения памяти см. Динамически распределяемая память.

Пример полной двоичной кучи

В информатике ку́ча (англ. heap) — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких, как алгоритм Дейкстры на d-кучах и сортировка методом пирамиды.

Структуру данных куча не следует путать с понятием куча в динамическом распределении памяти. Впервые термин использовался именно для структур данных. В некоторых ранних популярных языках программирования типа ЛИСП обеспечивалось динамическое распределение памяти с использованием структуры данных «куча», которая и дала своё имя выделяемому объёму памяти..

Кучи обычно реализуются в виде массивов, что исключает наличие указателей между её элементами.

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

• найти максимум или найти минимум: найти максимальный элемент в max-куче или минимальный элемент в min-куче, соответственно
• удалить максимум или удалить минимум: удалить корневой узел в max- или min-куче, соответственно
• увеличить ключ или уменьшить ключ: обновить ключ в max- или min-куче, соответственно
• добавить: добавление нового ключа в кучу.
• слияние: соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных.

Варианты

• 2-3 куча
• Двуродительская куча
• Двоичная куча
• Биномиальная куча
• Очередь Бродала
• Куча с D потомками
• Фибоначчиева куча
• Куча с приоритетом самого левого
• Спаренная куча
• Асимметричная куча
• Мягкая куча
• Тернарная куча
• Декартово дерево

Сравнение теоретических оценок вариантов

Ниже приведены оценки временно́й сложности вычислений для операций над некоторыми видами кучи. Там, где значение отмечено звездочкой, оценка сделана методом амортизационного анализа (по наихудшему времени), в остальных случаях оценка является регулярным худшим случаем. O(F) даёт асимптотическую верхнюю границу, а Θ(F) является асимптотически точной оценкой (см. обозначения «O» большое и «o» малое). Имена операций выбраны для min-кучи.

Операция	Двоичная	Биномиальная	Фибоначчиева	Спаренная	Бродал
найти минимум	Θ(1)	Θ(log n) or Θ(1)	Θ(1)	Θ(1)	Θ(1)
удалить минимум	Θ(log n)	Θ(log n)	O(log n)*	O(log n)*	O(log n)
добавить	Θ(log n)	O(log n)	Θ(1)	O(1)*	Θ(1)
уменьшить ключ	Θ(log n)	Θ(log n)	Θ(1)*	O(log n)*	Θ(1)
слияние	Θ(n)	O(log n)**	Θ(1)	O(1)*	Θ(1)

(*) Амортизационное время
(**) Где n — размер наибольшей кучи

Заметим, что «очередь Бродала» представляет собой реализацию очереди с параллельным приоритетом, разработанную группой во главе с Гертом Бродалом.

Применение

Структуры данных типа кучи имеют множество применений.

• Пирамидальная сортировка: один из лучших применяемых методов сортировки, не имеющий квадратичных наихудших сценариев.
• Алгоритмы поиска: при использовании кучи поиск минимума, максимума, того и другого, медианы или k-го наибольшего элемента может быть сделан за линейное время (часто даже за константное время).
• Алгоритмы на графах: Применение кучи в качестве структуры данных для внутреннего обхода даёт сокращение времени выполнения на полиномиальный порядок. Примерами таких проблем являются алгоритм построения минимального остовного дерева Прима и проблема кратчайшего пути Дейкстры.

Полная и почти полная бинарная куча может быть представлена очень эффективным способом с помощью индексного массива. Первый (или последний) элемент будет содержать корень. Следующие два элемента массива содержат узлы-потомки корня. Следующие четыре элемента содержат четверых потомков от двух узлов — потомков корня, и т. д. Таким образом, потомки узла уровня n будут расположены на позициях 2n и 2n+1 для массива, индексируемого с единицы, или на позициях 2n+1 и 2n+2 для массива, индексируемого с нуля. Это позволяет перемещаться вверх или вниз по дереву, выполняя простые вычисления индекса массива. Балансировка кучи делается перестановкой элементов, которые нарушают порядок. Поскольку мы можем построить кучу с помощью массива без дополнительной памяти (для узлов, например), то можно использовать пирамидальную сортировку для сортировки массива прямо на месте.

Реализации

• Стандартная библиотека шаблонов языка C++ предоставляет шаблоны функций для управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
• Набор шаблонов Java платформы Java 2 (начиная с версии 1.5) предоставляет реализацию бинарной кучи в классе java.util.PriorityQueue<E>.
• Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.
• Начиная с версии 5.3 PHP в стандартной библиотеке имеются методы maxheap (SplMaxHeap) и minheap (SplMinHeap).
• В Perl имеются реализации бинарной, биномиальной и фибоначчиевой кучи во всеобъемлющей сети архивов.

См. также

• Стек
• Алгоритм сортировки