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

редактировать
Структура данных информатики Пример двоичной максимальной кучи с ключами узлов целые числа от 1 до 100

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

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

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

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

Содержание

  • 1 Операции
  • 2 Реализация
  • 3 Варианты
  • 4 Сравнение теоретических оценок для вариантов
  • 5 Приложения
  • 6 Реализации
  • 7 См. Также
  • 8 Ссылки
  • 9 Внешние ссылки

Операции

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

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

Реализация

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

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

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

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

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

Варианты

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

Вот временные сложности различных структур данных кучи. Имена функций предполагают максимальную кучу. Значение «O (f)» и «Θ (f)» см. В нотации Big O.

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

Приложения

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

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

Реализации

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

См. Также

Ссылки

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

На Викискладе есть носители, связанные с Heap структуры данных.
В Wikibook Структуры данных есть страница по теме: Мин. и макс. кучи
  • Кучи в Wolfram MathWorld
  • Пояснение о том, как работают базовые алгоритмы кучи
  • Бентли, Джон Луис (2000). Жемчуг программирования (2-е изд.). Эддисон Уэсли. С. 147–162. ISBN 0201657880.
Последняя правка сделана 2021-05-23 04:27:56
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте