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

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

Пример полной бинарной кучи.

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

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

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

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

ВариантыПравить

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

Ниже приведены оценки временно́й сложности вычислений для операций над некоторыми видами кучи.^[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]

ПрименениеПравить

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

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

Полная и почти полная бинарная куча может быть представлена очень эффективным способом с помощью индексного массива. Первый (или последний) элемент будет содержать корень. Следующие два элемента массива содержат узлы-потомки корня. Следующие четыре элемента содержат четверых потомков от двух узлов — потомков корня, и т. д. Таким образом, потомки узла уровня 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]
Начиная с версии 5.3 PHP в стандартной библиотеке имеются методы maxheap (SplMaxHeap) и minheap (SplMinHeap).
В Perl имеются реализации бинарной, биномиальной и фибоначчиевой кучи во всеобъемлющей сети архивов.^[6]

См. такжеПравить

ПримечанияПравить

↑ ¹ ² ³ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill.
↑ Iacono, John (2000), Improved upper bounds for pairing heaps, Proc. 7th Scandinavian Workshop on Algorithm Theory, vol. 1851, Lecture Notes in Computer Science, Springer-Verlag, с. 63–77, DOI 10.1007/3-540-44985-X_5
↑ A Parallel Priority Queue with Constant Time Operations, <http://www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf> Архивная копия от 26 июля 2011 на Wayback Machine
↑ Frederickson, Greg N. (1993), An Optimal Algorithm for Selection in a Min-Heap, Information and Computation, vol. 104, Academic Press, с. 197–214, doi:10.1006/inco.1993.1030, <http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf> Архивная копия от 3 декабря 2012 на Wayback Machine
↑ Python heapq (неопр.). Дата обращения: 31 мая 2011. Архивировано 18 октября 2012 года.
↑ Perl Heap

[CLRS-1] ¹ ² ³ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill.

[Iacono-2] Iacono, John (2000), Improved upper bounds for pairing heaps, Proc. 7th Scandinavian Workshop on Algorithm Theory, vol. 1851, Lecture Notes in Computer Science, Springer-Verlag, с. 63–77, DOI 10.1007/3-540-44985-X_5

[3] A Parallel Priority Queue with Constant Time Operations, <http://www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf> Архивная копия от 26 июля 2011 на Wayback Machine

[4] Frederickson, Greg N. (1993), An Optimal Algorithm for Selection in a Min-Heap, Information and Computation, vol. 104, Academic Press, с. 197–214, doi:10.1006/inco.1993.1030, <http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf> Архивная копия от 3 декабря 2012 на Wayback Machine

[5] Python heapq (неопр.). Дата обращения: 31 мая 2011. Архивировано 18 октября 2012 года.

[6] Perl Heap

[1]

[2]

[3]

[4]

[5]

[6]