Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для кучи памяти (в компьютерном программировании низкого уровня), см выделение С динамической памятью .
Пример двоичной максимальной кучи с ключами узлов, являющимися целыми числами от 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 : переместить узел вниз по дереву, аналогично sift-up; используется для восстановления состояния кучи после удаления или замены.

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

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

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

В массиве первый индекс содержит корневой элемент. Следующие два индекса массива содержат потомков корня. Следующие четыре индекса содержат четырех потомков двух дочерних узлов корня и так далее. Следовательно, для узла с индексом i его дочерние элементы находятся в индексах 2i + 1 и 2i + 2 , а его родительский элемент находится на уровне индекса ((n-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]Это быстрее, чем последовательность последовательных вставок в изначально пустую кучу, которая является лог-линейной. [а]

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

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

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

Вот временные сложности [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 предоставляет интерфейс входного диапазона, который позволяет выполнять итерацию с помощью встроенных операторов foreach D и интеграцию с API-интерфейсом на основе диапазона пакета std.algorithm .
  • Платформа Java (начиная с версии 1.5) предоставляет реализацию двоичной кучи с классом java.util.PriorityQueueв Java Collections Framework . Этот класс по умолчанию реализует минимальную кучу; чтобы реализовать max-heap, программист должен написать собственный компаратор. Операции замены, увеличения / уменьшения или уменьшения / увеличения не поддерживаются.
  • В Python есть модуль heapq, который реализует очередь приоритетов с использованием двоичной кучи. Библиотека предоставляет функцию heapreplace для поддержки k-way слияния.
  • Начиная с версии 5.3 в стандартной библиотеке PHP есть как максимальная куча ( SplMaxHeap ), так и минимальная куча ( SplMinHeap ).
  • Perl имеет реализации двоичных, биномиальных и Фибоначчи куч в дистрибутиве Heap, доступном на CPAN .
  • Go язык содержит кучу пакет с кучей алгоритмов , которые работают на любом типе , который удовлетворяет данный интерфейс. Этот пакет не поддерживает операции замены, увеличения / уменьшения или уменьшения / увеличения.
  • Библиотека Apple Core Foundation содержит структуру CFBinaryHeap .
  • В Pharo есть реализация кучи в пакете Collections-Sequenceable вместе с набором тестовых примеров. Куча используется при реализации цикла событий таймера.
  • Язык программирования Rust имеет двоичную реализацию max-heap, BinaryHeap , в модуле коллекций своей стандартной библиотеки.

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

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

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

  1. ^ CORMEN, THOMAS 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) , 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
  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) от 2012-12-03 , получено 31.10.2010

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

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