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

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

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

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

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

Операции

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

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

Варианты

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

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

Операцияfind-maxудалить-максвставлятьключ увеличенияобъединить
Двоичный [8]Θ (1)Θ (журнал  n )O (журнал  n )O (журнал  n )Θ ( п )
ЛевыйΘ (1)Θ (журнал n )Θ (журнал n )O (журнал n )Θ (журнал n )
Биномиальный [8] [9]Θ (1)Θ (журнал n )Θ (1) [b]Θ (журнал n )O (log  n ) [c]
Фибоначчи [8] [10]Θ (1)O (log  n ) [b]Θ (1)Θ (1) [b]Θ (1)
Спаривание [11]Θ (1)O (log n ) [b]Θ (1)o (log  n ) [b] [d]Θ (1)
Бродал [14] [e]Θ (1)O (журнал  n )Θ (1)Θ (1)Θ (1)
Сочетание рангов [16]Θ (1)O (log n ) [b]Θ (1)Θ (1) [b]Θ (1)
Строгий Фибоначчи [17]Θ (1)O (журнал n )Θ (1)Θ (1)Θ (1)
2–3 кучи [18]O (журнал n )O (log n ) [b]O (log n ) [b]Θ (1)?
  1. ^ Каждая вставка занимает O (log ( k )) в существующем размере кучи, таким образом. С, постоянный множитель (половина) этих вставок находится в пределах постоянного множителя максимума, поэтому асимптотически мы можем предположить ; формально время. Это также легко увидеть из приближения Стирлинга .
  2. ^ a b c d e f g h i Амортизированное время.
  3. ^ n - размер большей кучи.
  4. ^ Нижняя граница[12] верхняя граница[13]
  5. ^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением ключа уменьшения, который не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). [15]

Приложения

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

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

См. Также

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

Ссылки

  1. ^ CORMEN, ТОМАС H. (2009). ВВЕДЕНИЕ В АЛГОРИТМЫ . Соединенные Штаты Америки: MIT Press Cambridge, Массачусетс, Лондон, Англия. С. 151–152. ISBN 978-0-262-03384-8.
  2. Перейти ↑ Black (ed.), Paul E. (2004-12-14). Запись о куче в Словаре алгоритмов и структур данных . Онлайн-версия. США Национальный институт стандартов и технологий , 14 декабря 2004 года Проверено на 2017-10-08 от https://xlinux.nist.gov/dads/HTML/heap.html .
  3. ^ Williams, JWJ (1964), "Алгоритм 232 - Пирамидальная сортировка", Связь по АКМ , 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 А. (2012), "Элементарные же Precise Наихудший анализ Heap-строительная программа Флойда", Fundamenta Informaticae , IOS Press, 120 (1): 75-92, DOI : 10,3233 / FI-2012-751.
  8. ^ a b c d Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
  9. ^ "Биномиальная куча | Блестящая математика и наука вики" . brilliant.org . Проверено 30 сентября 2019 .
  10. ^ Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . DOI : 10.1145 / 28869.28874 .  
  11. ^ Яконо, Джон (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
  12. ^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. DOI : 10.1145 / 320211.320214 .
  13. ^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. С. 174–183. CiteSeerX 10.1.1.549.471 . DOI : 10.1109 / SFCS.2005.75 . ISBN   0-7695-2468-0.
  14. ^ Бродал, Герт С. (1996), "Эффективные приоритетные очереди наихудшего случая" (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
  15. ^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Строительство кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.
  16. ^ Haeupler, Бернхард; Сен, Сиддхартха; Тарджан, Роберт Э. (ноябрь 2011 г.). "Куча ранговых пар" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. DOI : 10.1137 / 100785351 .
  17. ^ Бродал, Герт Стёльтинг ; Лагогианнис, Джордж; Тарджан, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. С. 1177–1184. CiteSeerX 10.1.1.233.1740 . DOI : 10.1145 / 2213977.2214082 . ISBN   978-1-4503-1245-5.
  18. ^ Такаок, Тадао (1999), Теория 2-3 куч (PDF) , стр. 12
  19. ^ Фредриксон, Грег Н. (1993), "Оптимальный алгоритм для выбора в Мин-Heap", информация и вычисления (PDF) , 104 , Academic Press, стр 197-214,. Дои : 10,1006 / inco.1993.1030 , архивируются из оригинала (PDF) от 03.12.2012 , извлечено 31.10.2010

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

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