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

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

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

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

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

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

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

Операции [ править ]

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

Базовый

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

Создание

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

Инспекция

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

Внутренний

увеличение ключа или уменьшение ключа : обновление ключа в максимальной или минимальной куче соответственно.
delete : удалить произвольный узел (с последующим перемещением последнего узла и просеиванием для сохранения кучи)
sift-up : перемещать узел вверх по дереву так долго, как это необходимо; используется для восстановления состояния кучи после вставки. Называется «просеять», потому что узел перемещается вверх по дереву, пока не достигнет нужного уровня, как в решете .
sift-down : переместить узел вниз по дереву, аналогично просеиванию вверх; используется для восстановления состояния кучи после удаления или замены.

Реализация [ править ]

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

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

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

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

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

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

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

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

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

Варианты [ править ]

Сравнение теоретических границ вариантов [ править ]

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

Операция	найти-макс	удалить-макс	вставлять	клавиша увеличения	сливаться
Двоичный ^[8]	я (1)	Θ (логарифм n )	О (логарифм n )	О (логарифм n )	Θ ( н )
Левый	я (1)	Θ (логарифм n )	Θ (логарифм n )	О (логарифм n )	Θ (логарифм n )
Биномиальный ^[8]^[9]	я (1)	Θ (логарифм n )	я (1) ^[б]	Θ (логарифм n )	О (логарифм n )
Наклонный бином ^[10]	я (1)	Θ (логарифм n )	я (1)	Θ (логарифм n )	О (логарифм n ) ^[с]
Сопряжение ^[11]	я (1)	О (логарифм n ) ^[б]	я (1)	о (логарифм n ) ^[б]^[д]	я (1)
Сопряжение по рангам ^[14]	я (1)	О (логарифм n ) ^[б]	я (1)	я (1) ^[б]	я (1)
Фибоначчи ^[8]^[15]	я (1)	О (логарифм n ) ^[б]	я (1)	я (1) ^[б]	я (1)
Строгий Фибоначчи ^[16]	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
Мостовая долина ^[17]^[Это]	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
2–3 кучи ^[19]	я (1)	О (логарифм n ) ^[б]	я (1) ^[б]	я (1)	О (логарифм n )

^ Каждая вставка занимает O(log( k )) существующего размера кучи, таким образом $\sum _{k=1}^{n}O(\log k)$ . С $\log n/2=(\log n)-1$ , постоянный коэффициент (половина) этих вставок находится в пределах постоянного коэффициента максимума, поэтому асимптотически мы можем предположить $k=n$ ; формально время $nO(\log n)-O(n)=O(n\log n)$ . Это также легко увидеть из приближения Стирлинга .
^ Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я Амортизированное время.
^ в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-max , delete-max , объединение в O (log n ).
^ Нижняя граница $\Omega (\log \log n),$ ^[12] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[13]
^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[18]

Приложения [ править ]

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

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

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

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

См. также [ править ]

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

Ссылки [ править ]

^ Блэк (редактор), Пол Э. (14 декабря 2004 г.). Запись о куче в Словаре алгоритмов и структур данных . Онлайн-версия. США Национальный институт стандартов и технологий , 14 декабря 2004 г. Получено 8 октября 2017 г. с https://xlinux.nist.gov/dads/HTML/heap.html .
^ КОРМЕН, ТОМАС Х. (2009). ВВЕДЕНИЕ В АЛГОРИТМЫ . Соединенные Штаты Америки: MIT Press Cambridge, Массачусетс, Лондон, Англия. стр. 151–152. ISBN 978-0-262-03384-8 .
^ Уильямс, JWJ (1964), «Алгоритм 232 — пирамидальная сортировка», Communications of the ACM , 7 (6): 347–348, doi : 10.1145/512274.512284
^ Стандартная библиотека Python, 8.4. heapq — Алгоритм очереди в куче, heapq.heappush
^ Стандартная библиотека Python, 8.4. heapq — Алгоритм очереди в куче, heapq.heappop
^ Стандартная библиотека Python, 8.4. heapq — Алгоритм очереди в куче, heapq.heapreplace
^ Сученек, Марек А. (2012), «Элементарный, но точный анализ наихудшего случая программы Флойда по построению кучи», Fundamenta Informaticae , 120 (1), IOS Press: 75–92, doi : 10.3233/FI-2012-751 .
^ Перейти обратно: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .
^ «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.
^ Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
^ Яконо, Джон (2000), «Улучшенные верхние границы для спаривания куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 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
^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .
^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .
^ Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .
^ Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .
^ Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .
^ Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .
^ Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12
^ Фредериксон, Грег Н. (1993), «Оптимальный алгоритм выбора в минимальной куче», Information and Computation (PDF) , vol. 104, Academic Press, стр. 197–214, doi : 10.1006/inco.1993.1030 , заархивировано из оригинала (PDF) 3 декабря 2012 г. , получено 31 октября 2010 г.

Внешние ссылки [ править ]

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

[8] Каждая вставка занимает O(log( k )) существующего размера кучи, таким образом $\sum _{k=1}^{n}O(\log k)$ . С $\log n/2=(\log n)-1$ , постоянный коэффициент (половина) этих вставок находится в пределах постоянного коэффициента максимума, поэтому асимптотически мы можем предположить $k=n$ ; формально время $nO(\log n)-O(n)=O(n\log n)$ . Это также легко увидеть из приближения Стирлинга .

[amortized-11] Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я Амортизированное время.

[13] в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-max , delete-max , объединение в O (log n ).

[pairingdecreasekey-17] Нижняя граница $\Omega (\log \log n),$ ^[12] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[13]

[brodal-23] Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[18]

[1] Блэк (редактор), Пол Э. (14 декабря 2004 г.). Запись о куче в Словаре алгоритмов и структур данных . Онлайн-версия. США Национальный институт стандартов и технологий , 14 декабря 2004 г. Получено 8 октября 2017 г. с https://xlinux.nist.gov/dads/HTML/heap.html .

[2] КОРМЕН, ТОМАС Х. (2009). ВВЕДЕНИЕ В АЛГОРИТМЫ . Соединенные Штаты Америки: MIT Press Cambridge, Массачусетс, Лондон, Англия. стр. 151–152. ISBN 978-0-262-03384-8 .

[3] Уильямс, JWJ (1964), «Алгоритм 232 — пирамидальная сортировка», Communications of the 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] Сученек, Марек А. (2012), «Элементарный, но точный анализ наихудшего случая программы Флойда по построению кучи», Fundamenta Informaticae , 120 (1), IOS Press: 75–92, doi : 10.3233/FI-2012-751 .

[CLRS-9] Перейти обратно: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .

[10] «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.

[12] Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x

[Iacono-14] Яконо, Джон (2000), «Улучшенные верхние границы для спаривания куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 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

[Fredman1999-15] Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .

[16] Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .

[18] Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .

[Fredman_And_Tarjan-19] Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .

[20] Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .

[21] Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.

[22] Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .

[24] Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12

[25] Фредериксон, Грег Н. (1993), «Оптимальный алгоритм выбора в минимальной куче», Information and Computation (PDF) , vol. 104, Academic Press, стр. 197–214, doi : 10.1006/inco.1993.1030 , заархивировано из оригинала (PDF) 3 декабря 2012 г. , получено 31 октября 2010 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[а]

[8]

[9]

[б]

[10]

[с]

[11]

[д]

[14]

[15]

[16]

[17]

[Это]

[19]

[12]

[13]

[18]

[20]

v т Это Древовидные структуры данных
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v т Это Структуры данных
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures