Куча (структура данных) - Heap (data structure)

Для кучи памяти (в компьютерном программировании низкого уровня), см выделение С динамической памятью .
Пример двоичной максимальной кучи с ключами узлов, являющимися целыми числами от 1 до 100

В информатике , куча является специализированным дерево основанной структуры данных , которая является по существу почти полное деревом , которое удовлетворяет свойство кучи : в максимальной куче , для любого заданного узла C, если P является родительским узлом C, то ключ ( значение ) P больше или равно ключу C. В минимальной куче ключ P меньше или равен ключу C. Узел на «вершине» кучи (без родители) называется корневым узлом.

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

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

Обратите внимание, что, как показано на рисунке, нет подразумеваемого упорядочивания между братьями и сестрами или кузенами и не подразумевается последовательность для обхода по порядку (как это было бы, например, в двоичном дереве поиска ). Вышеупомянутое отношение кучи применяется только между узлами и их родителями, дедушками и бабушками и т. Д. Максимальное количество дочерних узлов, которое может иметь каждый узел, зависит от типа кучи.

Операции

Общие операции с кучей:

Базовый
  • find-max (или find-min ): найти максимальный элемент max-heap или минимальный элемент min-heap, соответственно (также известный как peek )
  • insert : добавление нового ключа в кучу (он же push )
  • extract-max (или extract-min ): возвращает узел максимального значения из максимальной кучи [или минимальное значение из минимальной кучи] после удаления его из кучи (также известного как pop )
  • delete-max (или delete-min ): удаление корневого узла максимальной кучи (или минимальной кучи) соответственно
  • заменить : извлечь корень и нажать новый ключ. Более эффективен, чем pop с последующим push, так как нужно балансировать только один раз, а не дважды, и подходит для куч фиксированного размера.
Творчество
  • create-heap : создать пустую кучу
  • heapify : создать кучу из заданного массива элементов
  • merge ( объединение ): объединение двух куч для формирования действительной новой кучи, содержащей все элементы обоих, с сохранением исходных куч.
  • meld : объединение двух куч для формирования действительной новой кучи, содержащей все элементы обеих, уничтожение исходных куч.
Осмотр
  • size : вернуть количество элементов в куче.
  • is-empty : вернуть true, если куча пуста, иначе false.
Внутренний
  • Увеличить-ключ или уменьшить-ключ : обновление ключа в пределах максимальной или минимальной кучи, соответственно
  • delete : удалить произвольный узел (с последующим перемещением последнего узла и просеиванием для сохранения кучи)
  • sift-up : перемещать узел вверх по дереву на столько, сколько необходимо; используется для восстановления состояния кучи после вставки. Называется «просеивание», потому что узел перемещается вверх по дереву, пока не достигнет нужного уровня, как в сите .
  • sift-down : переместить узел вниз по дереву, аналогично просеиванию вверх; используется для восстановления состояния кучи после удаления или замены.

Реализация

Кучи обычно реализуются с помощью массива следующим образом:

  • Каждый элемент в массиве представляет собой узел кучи, а
  • Отношения родитель / потомок неявно определяются индексами элементов в массиве.
Пример полной двоичной максимальной кучи с ключами узлов, являющимися целыми числами от 1 до 100, и то, как она будет храниться в массиве.

Для двоичной кучи в массиве первый индекс содержит корневой элемент. Следующие два индекса массива содержат потомков корня. Следующие четыре индекса содержат четырех потомков двух дочерних узлов корня и так далее. Следовательно, для узла с индексом i его дочерние элементы находятся в индексах 2i + 1 и 2i + 2 , а его родительский элемент - с индексом ⌊ (i − 1) / 2⌋ . Эта простая схема индексации позволяет эффективно перемещаться «вверх» или «вниз» по дереву.

Балансировка кучи выполняется с помощью операций sift-up или sift-down (замена вышедших из строя элементов). Поскольку мы можем построить кучу из массива, не требуя дополнительной памяти (например, для узлов), heapsort можно использовать для сортировки массива на месте.

После того, как элемент вставлен в кучу или удален из нее, свойство кучи может быть нарушено, и куча должна быть повторно сбалансирована путем замены элементов в массиве.

Хотя разные типы кучи реализуют операции по-разному, но наиболее распространенный способ выглядит следующим образом:
Вставка: добавить новый элемент в конец кучи, в первое доступное свободное пространство. Это нарушит свойство кучи, поэтому элементы будут сдвинуты вверх (или операция плавания ) до тех пор, пока свойство кучи не будет восстановлено.
Извлечение: удалите корень и вставьте последний элемент кучи в корень, и это нарушит свойство кучи, поэтому выполните просеивание, чтобы восстановить свойство кучи (или операцию поглощения ). Таким образом, замена выполняется путем удаления корня и помещения нового элемента в корень и просеивания вниз, избегая этапа просеивания по сравнению с pop (отсеивание последнего элемента) с последующим push (отсеивание нового элемента).

Построение двоичной (или d- мерной) кучи из заданного массива элементов может быть выполнено за линейное время с использованием классического алгоритма Флойда с числом сравнений в наихудшем случае, равным 2 N - 2 с 2 ( N ) - e 2 ( N ) (для двоичной кучи), где s 2 ( N ) - это сумма всех цифр двоичного представления N, а e 2 ( N ) - показатель степени 2 в разложении N на простые множители . Это быстрее, чем последовательность последовательных вставок в изначально пустую кучу, которая является лог-линейной.

Варианты

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

Вот временные сложности различных структур данных кучи. Имена функций предполагают максимальную кучу. Для значения " O ( F )" и " thetas ; ( е )" см Big O нотацию .

Операция find-max удалить-макс вставлять ключ увеличения объединить
Двоичный Θ (1) Θ (журнал  n ) O (журнал  n ) O (журнал  n ) Θ ( п )
Левый Θ (1) Θ (журнал n ) Θ (журнал n ) O (журнал n ) Θ (журнал n )
Биномиальный Θ (1) Θ (журнал n ) Θ (1) Θ (журнал n ) O (журнал  n )
Фибоначчи Θ (1) O (журнал  n ) Θ (1) Θ (1) Θ (1)
Сопряжение Θ (1) O (журнал n ) Θ (1) o (войти  n ) Θ (1)
Brodal Θ (1) O (журнал  n ) Θ (1) Θ (1) Θ (1)
Ранговые пары Θ (1) O (журнал n ) Θ (1) Θ (1) Θ (1)
Строгий Фибоначчи Θ (1) O (журнал n ) Θ (1) Θ (1) Θ (1)
2–3 кучи O (журнал n ) O (журнал n ) O (журнал n ) Θ (1) ?

Приложения

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

  • Heapsort : один из лучших методов сортировки на месте и без квадратичных сценариев наихудшего случая.
  • Алгоритмы выбора : куча позволяет получить доступ к минимальному или максимальному элементу в постоянное время, а другой выбор (например, медиана или k-й элемент) может быть выполнен в сублинейном времени для данных, которые находятся в куче.
  • Алгоритмы графа : при использовании кучи в качестве структур данных внутреннего обхода время выполнения будет уменьшено на полиномиальный порядок. Примерами таких проблем являются алгоритм минимального остовного дерева Прима и алгоритм кратчайшего пути Дейкстры .
  • Очередь с приоритетом : очередь с приоритетом - это абстрактное понятие, такое как «список» или «карта»; точно так же, как список может быть реализован с помощью связанного списка или массива, очередь с приоритетом может быть реализована с помощью кучи или множества других методов.
  • K-way merge : структура данных кучи полезна для объединения многих уже отсортированных входных потоков в один отсортированный выходной поток. Примеры необходимости слияния включают внешнюю сортировку и потоковую передачу результатов из распределенных данных, таких как структурированное дерево слияния с журналом. Внутренний цикл получает элемент min, заменяет его следующим элементом для соответствующего входного потока, а затем выполняет операцию отсеивания кучи. (В качестве альтернативы функция замены.) (Использование функций extract-max и insert для очереди с приоритетами гораздо менее эффективно.)
  • Статистика заказа : структура данных Heap может использоваться для эффективного поиска k-го наименьшего (или наибольшего) элемента в массиве.

Реализации языков программирования

  • ++ Стандартная библиотека С обеспечивает make_heap , push_heap и pop_heap алгоритмы для куч (обычно реализован в виде двоичных куч), которые работают на произвольной произвольный доступ итераторы . Он обрабатывает итераторы как ссылку на массив и использует преобразование массива в кучу. Он также предоставляет контейнерный адаптер priority_queue , который объединяет эти средства в контейнер, подобный классу. Однако нет стандартной поддержки для операций замены, увеличения / уменьшения или уменьшения / увеличения.
  • Библиотеки Boost C ++ включают библиотеку кучи. В отличие от STL, он поддерживает операции уменьшения и увеличения, а также поддерживает дополнительные типы кучи: в частности, он поддерживает d -ary, биномиальный, Фибоначчи, спаривание и перекос кучи.
  • Существует общая реализация кучи для C и C ++ с поддержкой D-ичной кучи и B-кучи . Он предоставляет API в стиле STL.
  • Стандартная библиотека на языке программирования D включает в себя std.container.BinaryHeap , который реализуется в терминах двойки диапазонов . Экземпляры могут быть созданы из любого диапазона произвольного доступа . BinaryHeap предоставляет интерфейс входного диапазона, который позволяет выполнять итерацию с помощью встроенных в D операторов foreach и интеграцию с API-интерфейсом на основе диапазона пакета std.algorithm .
  • Платформа Java (начиная с версии 1.5) предоставляет реализацию двоичной кучи с классом java.util.PriorityQueueв Java Collections Framework . Этот класс по умолчанию реализует минимальную кучу; чтобы реализовать максимальную кучу, программист должен написать собственный компаратор. Операции замены, увеличения / уменьшения или уменьшения / увеличения не поддерживаются.
  • В Python есть модуль heapq, который реализует очередь приоритетов с использованием двоичной кучи. Библиотека предоставляет функцию heapreplace для поддержки k-way слияния.
  • PHP имеет как максимальную кучу ( SplMaxHeap ), так и минимальную кучу ( SplMinHeap ), начиная с версии 5.3 в стандартной библиотеке PHP.
  • Perl имеет реализации двоичных, биномиальных и Фибоначчи куч в дистрибутиве кучи, доступном на CPAN .
  • Go язык содержит кучу пакет с кучей алгоритмов , которые работают на любом типе , который удовлетворяет данный интерфейс. Этот пакет не поддерживает операции замены, увеличения / уменьшения или уменьшения / увеличения.
  • Библиотека Apple Core Foundation содержит структуру CFBinaryHeap .
  • В Pharo есть реализация кучи в пакете Collections-Sequenceable вместе с набором тестовых примеров. Куча используется при реализации цикла событий таймера.
  • Язык программирования Rust имеет двоичную реализацию максимальной кучи, BinaryHeap , в модуле коллекций своей стандартной библиотеки.

Смотрите также

использованная литература

внешние ссылки

  • Куча в Wolfram MathWorld
  • Объяснение того, как работают основные алгоритмы кучи
  • Бентли, Джон Луи (2000). Жемчуг программирования (2-е изд.). Эддисон Уэсли. С. 147–162. ISBN 0201657880.