✖


Jump to content

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

(Перенаправлено с Heapselect )
Информацию о куче памяти (в низкоуровневом компьютерном программировании), которая не связана с этой структурой данных, см. в разделе распределение памяти C. Динамическое
Пример двоичной максимальной кучи, где ключи узла представляют собой целые числа от 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 , его дочерние элементы находятся с индексами ⁠ ⁠ и ⁠ ⁠ , а его родительский элемент имеет индекс ⌊( i −1)/2⌋ . Эта простая схема индексации позволяет эффективно перемещаться «вверх» или «вниз» по дереву.

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

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

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

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

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

Варианты

[ редактировать ]

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

[ редактировать ]

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

Операция найти-макс удалить-макс клавиша увеличения вставлять сливаться помойка [б]
Двоичный [8] я (1) Θ (логарифм n ) Θ (логарифм n ) Θ (логарифм n ) Θ ( н ) Θ ( н )
Перекос [9] я (1) О (log n ) утра. О (log n ) утра. О (log n ) утра. О (log n ) утра. Θ ( н ) утра.
Левый [10] я (1) Θ (логарифм n ) Θ (логарифм n ) Θ (логарифм n ) Θ (логарифм n ) Θ ( н )
Биномиальный [8] [12] я (1) Θ (логарифм n ) Θ (логарифм n ) Θ (1) утра. Θ (логарифм n ) [с] Θ ( н )
Наклонный бином [13] я (1) Θ (логарифм n ) Θ (логарифм n ) я (1) Θ (логарифм n ) [с] Θ ( н )
2–3 кучи [15] я (1) О (log n ) утра. я (1) Θ (1) утра. О (логарифм n ) [с] Θ ( н )
Перекос снизу вверх [9] я (1) О (log n ) утра. О (log n ) утра. Θ (1) утра. Θ (1) утра. Θ ( н ) утра.
Сопряжение [16] я (1) О (log n ) утра. о (log n ) утра. [д] я (1) я (1) Θ ( н )
Сопряжение по рангам [19] я (1) О (log n ) утра. Θ (1) утра. я (1) я (1) Θ ( н )
Фибоначчи [8] [20] я (1) О (log n ) утра. Θ (1) утра. я (1) я (1) Θ ( н )
Строгий Фибоначчи [21] [и] я (1) Θ (логарифм n ) я (1) я (1) я (1) Θ ( н )
Мостовая долина [22] [и] я (1) Θ (логарифм n ) я (1) я (1) я (1) Θ ( н ) [23]
  1. ^ Каждая вставка занимает O(log( k )) существующего размера кучи, таким образом . С , постоянный коэффициент (половина) этих вставок находится в пределах постоянного коэффициента максимума, поэтому асимптотически мы можем предположить ; формально время . Это также легко увидеть из приближения Стирлинга .
  2. ^ make-heap — это операция построения кучи из последовательности из n неотсортированных элементов. Это можно сделать за время Θ ( n ), когда объединение выполняется за время O (log n ) (при этом обе сложности могут быть амортизированы). [9] [10] Другой алгоритм достигает Θ ( n ) для двоичных куч. [11]
  3. ^ Перейти обратно: а б с Для постоянных куч (не поддерживающих увеличения-ключа ) общее преобразование снижает стоимость объединения до стоимости вставки , в то время как новая стоимость удаления-макс является суммой старых затрат удаления-макс и объединения . [14] Здесь он выполняет объединение за время Θ (1) (амортизируется, если стоимость вставки равна), в то время как delete-max все еще выполняется за O (log n ). Применительно к косым биномиальным кучам он дает очереди Бродала-Окасаки, постоянные кучи с оптимальной сложностью для наихудшего случая. [13]
  4. ^ Нижняя граница [17] верхняя граница [18]
  5. ^ Перейти обратно: а б Очереди Бродала и строгие кучи Фибоначчи обеспечивают оптимальную сложность кучи в наихудшем случае. Впервые они были описаны как императивные структуры данных. Очередь Бродала-Окасаки представляет собой постоянную структуру данных, обеспечивающую тот же оптимум, за исключением того, что ключ увеличения не поддерживается.

Приложения

[ редактировать ]

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

  • Heapsort : один из лучших методов сортировки, имеющий место и не допускающий квадратичных наихудших сценариев.
  • Алгоритмы выбора : куча обеспечивает доступ к минимальному или максимальному элементу за постоянное время, а другие выборы (например, медиана или k-й элемент) могут выполняться за сублинейное время для данных, находящихся в куче. [24]
  • Алгоритмы графов . Благодаря использованию кучи в качестве внутренних структур данных обхода время выполнения будет сокращено на полиномиальный порядок. Примерами таких задач являются алгоритм минимального остовного дерева Прима и алгоритм поиска кратчайшего пути Дейкстры .
  • Очередь с приоритетом . Очередь с приоритетом — это абстрактное понятие, такое как «список» или «карта»; точно так же, как список может быть реализован с помощью связанного списка или массива, очередь с приоритетами может быть реализована с помощью кучи или множества других методов.
  • 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.

См. также

[ редактировать ]

Ссылки

[ редактировать ]
  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 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 .
  8. ^ Перейти обратно: а б с д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03141-8 .
  9. ^ Перейти обратно: а б с Слитор, Дэниел Доминик ; Тарьян, Роберт Эндре (февраль 1986 г.). «Саморегулирующиеся кучи» . SIAM Journal по вычислительной технике . 15 (1): 52–69. CiteSeerX   10.1.1.93.6678 . дои : 10.1137/0215004 . ISSN   0097-5397 .
  10. ^ Перейти обратно: а б Тарьян, Роберт (1983). «3.3. Левые кучи». Структуры данных и сетевые алгоритмы . стр. 38–42. дои : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5 .
  11. ^ Хейворд, Райан; МакДиармид, Колин (1991). «Анализ среднего случая построения кучи путем повторной вставки» (PDF) . Дж. Алгоритмы . 12 : 126–153. CiteSeerX   10.1.1.353.7888 . дои : 10.1016/0196-6774(91)90027-в . Архивировано из оригинала (PDF) 5 февраля 2016 г. Проверено 28 января 2016 г.
  12. ^ «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.
  13. ^ Перейти обратно: а б Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 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), «Улучшенные верхние границы для спаривания куч», 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
  17. ^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .
  18. ^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX   10.1.1.549.471 . дои : 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 . дои : 10.1145/28869.28874 .
  21. ^ Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX   10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN  978-1-4503-1245-5 .
  22. ^ Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 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) , vol. 104, Academic Press, стр. 197–214, doi : 10.1006/inco.1993.1030 , заархивировано из оригинала (PDF) 3 декабря 2012 г. , получено 31 октября 2010 г.
[ редактировать ]
В Wikimedia Commons есть медиафайлы, связанные со структурами данных кучи .
Wikibook В структурах данных есть страница на тему: Минимальные и максимальные кучи.
  • Куча в Wolfram MathWorld
  • Объяснение того, как работают основные алгоритмы кучи.
  • Бентли, Джон Луи (2000). Жемчуг программирования (2-е изд.). Эддисон Уэсли. стр. 147–162. ISBN  0201657880 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Heap_(data_structure)&oldid=1238116147#Applications"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f69d2f7a0ef910fe54c28fce19064dfc__1722568320
URL1:https://arc.ask3.ru/arc/aa/f6/fc/f69d2f7a0ef910fe54c28fce19064dfc.html
Заголовок, (Title) документа по адресу, URL1:
Heap (data structure) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)