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

Структура данных компьютерных наук

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

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

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

Распространенной реализацией кучи является двоичная куча , в которой дерево представляет собой полное ^[2] двоичное дерево (см. рисунок). Структура данных кучи, в частности двоичная куча, была введена Дж. У. Дж. Уильямсом в 1964 году как структура данных для алгоритма сортировки пирамидальной сортировки . ^[3] Кучи также играют решающую роль в нескольких эффективных алгоритмах графов, таких как алгоритм Дейкстры . Когда куча представляет собой полное двоичное дерево, она имеет наименьшую возможную высоту — куча с N узлами и a ветвями для каждого узла всегда имеет log _a N высоты.

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

Кучи обычно создаются на месте в том же массиве, где хранятся элементы, при этом их структура подразумевается в шаблоне доступа операций. Кучи отличаются этим от других структур данных с похожими или в некоторых случаях лучшими теоретическими границами, такими как деревья Radix, тем, что они не требуют дополнительной памяти, кроме той, которая используется для хранения ключей.

Операции

Обычные операции с кучами:

Базовый

• find-max (или find-min ): найти максимальный элемент max-heap или минимальный элемент min-heap соответственно (также известный как peek )
• вставка : добавление нового ключа в кучу (иначе говоря, push ^[4] )
• extract-max (или extract-min ): возвращает узел максимального значения из максимальной кучи [или минимального значения из минимальной кучи] после его удаления из кучи (он же pop ^[5] )
• delete-max (или delete-min ): удаление корневого узла максимальной кучи (или минимальной кучи) соответственно
• заменить : вытащить корень и вставить новый ключ. Это эффективнее, чем вытащить с последующим вставлением, поскольку балансировка требуется только один раз, а не дважды, и подходит для куч фиксированного размера. ^[6]

Создание

• create-heap : создать пустую кучу
• heapify : создать кучу из заданного массива элементов
• merge ( union ): объединение двух куч для формирования новой допустимой кучи, содержащей все элементы обеих, с сохранением исходных куч.
• объединение : объединение двух куч для формирования новой допустимой кучи, содержащей все элементы обеих, с уничтожением исходных куч.

Инспекция

• размер : возвращает количество элементов в куче.
• is-empty : возвращает true, если куча пуста, в противном случае возвращает false.

Внутренний

• Increase-key или Reduce-key : обновление ключа в пределах max- или min-heap соответственно
• удалить : удалить произвольный узел (с последующим перемещением последнего узла и просеиванием для сохранения кучи)
• sift-up : переместить узел вверх по дереву, пока это необходимо; используется для восстановления состояния кучи после вставки. Называется "sift", потому что узел перемещается вверх по дереву, пока не достигнет нужного уровня, как в решете .
• sift-down : перемещает узел вниз по дереву, аналогично sift-up; используется для восстановления состояния кучи после удаления или замены.

Выполнение

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

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

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

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

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

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

Хотя разные типы куч реализуют операции по-разному, наиболее распространенный способ выглядит следующим образом:

• Вставка: Добавить новый элемент в конец кучи, в первое доступное свободное пространство. Если это нарушит свойство кучи, просеять новый элемент ( операция swim ) до тех пор, пока свойство кучи не будет восстановлено.
• Извлечение: Удалите корень и вставьте последний элемент кучи в корень. Если это нарушит свойство кучи, просейте новый корень ( операция sink ), чтобы восстановить свойство кучи.
• Замена: Удалите корень и поместите новый элемент в корень и просейте вниз. По сравнению с извлечением, за которым следует вставка, это позволяет избежать шага просеивания вверх.

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

Варианты

• 2–3 кучи
• B-куча
• Бип
• Двоичная куча
• Биномиальная куча
• очередь Бродала
• d -арная куча
• Куча Фибоначчи
• Куча КД
• Куча листьев
• Левая куча
• Косая биномиальная куча
• Строгая куча Фибоначчи
• Мин-макс куча
• Сопряжение кучи
• Радикальная куча
• Рандомизированная объединяемая куча
• Косая куча
• Мягкая куча
• Тройная куча
• Треп
• Слабая куча

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

Вот временные сложности ^[8] различных структур данных кучи. Сокращение am. указывает, что данная сложность амортизирована, в противном случае это сложность наихудшего случая. Для значения " O ( f )" и " Θ ( f )" см . нотацию Big O. Имена операций предполагают максимальную кучу.

1. Каждая вставка занимает O(log( k )) в существующем размере кучи, таким образом . Поскольку , постоянный множитель (половина) этих вставок находятся в пределах постоянного множителя от максимума, поэтому асимптотически мы можем предположить ; формально время равно . Это также можно легко увидеть из приближения Стирлинга . ${\displaystyle \sum _{k=1}^{n}O(\log k)}$ ${\displaystyle \log n/2=(\log n)-1}$ ${\displaystyle k=n}$ ${\displaystyle nO(\log n)-O(n)=O(n\log n)}$
2. make-heap — это операция построения кучи из последовательности из n неотсортированных элементов. Она может быть выполнена за время Θ ( n ), когда meld выполняется за время O (log  n ) (где обе сложности могут быть амортизированы). ^{[9] [10]} Другой алгоритм достигает Θ ( n ) для двоичных куч. ^[11]
3. Для постоянных куч (не поддерживающих Increase-key ) универсальное преобразование снижает стоимость meld до стоимости insert , в то время как новая стоимость delete-max является суммой старых стоимостей delete-max и meld . ^[14] Здесь это заставляет meld работать за Θ (1) время (амортизированное, если стоимость insert равна ), в то время как delete-max по-прежнему работает за O (log  n ). Применительно к перекошенным биномиальным кучам это дает очереди Бродала-Окасаки, постоянные кучи с оптимальной сложностью в худшем случае. ^[13]
4. Нижняя граница ^[17] верхняя граница ^[18] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
5. Очереди Бродала и строгие кучи Фибоначчи достигают оптимальных сложностей в худшем случае для куч. Они были впервые описаны как императивные структуры данных. Очередь Бродала-Окасаки — это постоянная структура данных, достигающая того же оптимума, за исключением того, что Increase-key не поддерживается.

Приложения

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

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

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

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

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

• Алгоритм сортировки
• Структура данных поиска
• Стек (абстрактный тип данных)
• Очередь (абстрактный тип данных)
• Дерево (структура данных)
• Treap — форма двоичного дерева поиска, основанная на упорядоченных в куче деревьях.

Ссылки

1. Black (ред.), Paul E. (14.12.2004). Статья о куче в словаре алгоритмов и структур данных . Онлайн-версия. Национальный институт стандартов и технологий США , 14 декабря 2004 г. Получено 08.10.2017 с https://xlinux.nist.gov/dads/HTML/heap.html.
2. КОРМЕН, ТОМАС Х. (2009). ВВЕДЕНИЕ В АЛГОРИТМЫ . Соединенные Штаты Америки: Издательство MIT, Кембридж, Массачусетс, Лондон, Англия. С. 151–152. ISBN 978-0-262-03384-8.
3. Уильямс, JWJ (1964), «Алгоритм 232 — Пирамидальная сортировка», Сообщения ACM , 7 (6): 347–348, doi :10.1145/512274.512284
4. Стандартная библиотека Python, 8.4. heapq — Алгоритм очереди кучи, heapq.heappush
5. Стандартная библиотека Python, 8.4. heapq — Алгоритм очереди кучи, heapq.heappop
6. Стандартная библиотека Python, 8.4. heapq — Алгоритм очереди кучи, heapq.heapreplace
7. Suchenek, Marek A. (2012), «Элементарный, но точный анализ худшего случая программы построения кучи Флойда», Fundamenta Informaticae , 120 (1), IOS Press: 75–92, doi :10.3233/FI-2012-751.
8. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
9. Sleator, Daniel Dominic ; Tarjan, Robert Endre (февраль 1986). «Саморегулирующиеся кучи». SIAM Journal on Computing . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
10. Tarjan, Robert (1983). "3.3. Левые кучи". Структуры данных и сетевые алгоритмы . стр. 38–42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
11. Хейворд, Райан; МакДиармид, Колин (1991). "Анализ среднего случая построения кучи путем повторной вставки" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Архивировано из оригинала (PDF) 2016-02-05 . Получено 2016-01-28 . 
12. "Биномиальная куча | Brilliant Math & Science Wiki". brilliant.org . Получено 2019-09-30 .
13. Brodal, Gerth Stølting; Okasaki, Chris (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди с приоритетами», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
14. Окасаки, Крис (1998). "10.2. Структурная абстракция". Чисто функциональные структуры данных (1-е изд.). С. 158–162. ISBN 9780521631242.
15. Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12
16. Яконо, Джон (2000), «Улучшенные верхние границы для парных куч», Труды 7-го Скандинавского семинара по теории алгоритмов (PDF) , Lecture Notes in Computer Science, т. 1851, Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5, ISBN  3-540-67690-2
17. Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности парных куч и связанных с ними структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. doi :10.1145/320211.320214.
18. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . Труды FOCS '05 46-го ежегодного симпозиума IEEE по основам компьютерной науки. стр. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN  0-7695-2468-0.
19. Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351.
20. Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
21. Бродал, Герт Столтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Труды 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi :10.1145/2213977.2214082. ISBN  978-1-4503-1245-5.
22. Бродал, Герт С. (1996), «Эффективные очереди с приоритетами в наихудшем случае» (PDF) , Труды 7-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 52–58
23. Гудрич, Майкл Т .; Тамассиа, Роберто (2004). "7.3.6. Построение кучи снизу вверх". Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.
24. Фредериксон, Грег Н. (1993), «Оптимальный алгоритм выбора в минимальной куче», Information and Computation (PDF) , т. 104, Academic Press, стр. 197–214, doi : 10.1006/inco.1993.1030 , заархивировано из оригинала (PDF) 2012-12-03 , извлечено 2010-10-31

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

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