21-10-2023
В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких как алгоритм Дейкстры и сортировка методом пирамиды.
Структуру данных куча не следует путать с понятием куча в динамическом распределении памяти. Впервые термин использовался именно для структур данных. В некоторых ранних популярных языках программирования типа ЛИСП обеспечивалось динамическое распределение памяти с использованием структуры данных «куча», которая и дала своё имя выделяемому объёму памяти.[1].
Кучи обычно реализуются в виде массивов, что исключает наличие указателей между её элементами.
Над кучами обычно проводятся следующие операции:
Содержание |
Ниже приведены оценки временно́й сложности вычислений для операций над некоторыми видами кучи.[1] Там, где значение отмечено звездочкой, оценка сделана методом амортизационного анализа (по наихудшему времени), в остальных случаях оценка является регулярным худшим случаем. O(F) даёт асимптотическую верхнюю границу, а Θ(F) является асимптотически точной оценкой (см. обозначения «O» большое и «o» малое). Имена операций выбраны для min-кучи.
Операция | Двоичная | Биномиальная | Фибоначчиева | Спаренная[2] | Бродал |
---|---|---|---|---|---|
найти минимум | Θ(1) | Θ(log n) or Θ(1) | Θ(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 — размер наибольшей кучи
Заметим, что «очередь Бродала» представляет собой реализацию очереди с параллельным приоритетом, разработанную группой во главе с Гертом Бродалом.[3]
Структуры данных типа кучи имеют множество применений.
Полная и почти полная бинарная куча может быть представлена очень эффективным способом с помощью индексного массива. Первый (или последний) элемент будет содержать корень. Следующие два элемента массива содержат узлы-потомки корня. Следующие четыре элемента содержат четверых потомков от двух узлов — потомков корня, и т.д. Таким образом, потомки узла уровня n
будут расположены на позициях 2n
и 2n+1
для массива, индексируемого с единицы, или на позициях 2n+1
и 2n+2
для массива, индексируемого с нуля. Это позволяет перемещаться вверх или вниз по дереву, выполняя простые вычисления индекса массива. Балансировка кучи делается перестановкой элементов, которые нарушают порядок. Поскольку мы можем построить кучу с помощью массива без дополнительной памяти (для узлов, например), то можно использовать пирамидальную сортировку для сортировки массива прямо на месте.
Куча (структура данных).