d -ary куча

$Д$ -ичные куч или $д$ -heap является приоритетной очередью структуры данных , обобщение двоичной кучи , в которой узлы имеют $d$ детей вместо 2. ^[1]^[2]^[3] Таким образом, двоичные кучи 2 -heap, а тройная куча - это 3-куча. Согласно Тарьяну ^[2] и Дженсену и др. ^[4] $д-$ рные кучи были изобретены Дональдом Б. Джонсоном в 1975 году ^[1].

Эта структура данных позволяет выполнять операции с пониженным приоритетом быстрее, чем двоичные кучи, за счет более медленных минимальных операций удаления. Этот компромисс приводит к лучшему времени выполнения таких алгоритмов, как алгоритм Дейкстры, в котором операции уменьшения приоритета более распространены, чем операции удаления min. ^[1]^[5] Кроме того, $d$ -ary кучи имеют лучшее поведение кеш-памяти, чем двоичные кучи, что позволяет им работать быстрее на практике, несмотря на теоретически большее время работы в худшем случае. ^[6] Как и двоичные кучи, $d$ -ary кучи представляют собой внутреннюю структуру данных.который не использует дополнительного хранилища, кроме необходимого для хранения массива элементов в куче. ^[2]^[7]

Структура данных [ править ]

$Д$ -ичные кучи состоят из массива из $п$ элементов, каждый из которых имеет приоритет , связанный с ним. Эти элементы можно рассматривать как узлы в полном $d-$ арном дереве, перечисленные в порядке обхода в первую очередь в ширину : элемент в позиции 0 массива (с использованием нумерации с отсчетом от нуля ) формирует корень дерева, элементы в позициях 1 через $d$ являются его $дочерними$ элементами , следующие $d 2$ элемента являются его внуками и т. д. Таким образом, родительский элемент элемента в позиции $i$ (для любого $i > 0$ ) является элементом в позиции $⌊ (i - 1) / d ⌋$ а его дочерние элементы - элементы в позициях от $di + 1$ до $di + d$ . Согласно свойству кучи , в минимальной куче каждый элемент имеет приоритет, по крайней мере, такой же большой, как и его родительский элемент; в максимальной куче каждый элемент имеет приоритет не больше, чем его родительский элемент. ^[2]^[3]

Элемент с минимальным приоритетом в минимальной куче (или элемент с максимальным приоритетом в максимальной куче) всегда можно найти в позиции 0 массива. Чтобы удалить этот элемент из очереди приоритетов, последний элемент x в массиве перемещается на его место, а длина массива уменьшается на единицу. Затем, в то время как элемент x и его дочерние элементы не удовлетворяют свойству кучи, элемент x заменяется одним из его дочерних элементов (тот, у которого наименьший приоритет в минимальной куче, или тот, у которого наибольший приоритет в максимальной куче) , перемещая его вниз в дереве, а затем в массиве, пока в конечном итоге свойство кучи не будет выполнено. Та же процедура перестановки вниз может использоваться для увеличения приоритета элемента в минимальной куче или для уменьшения приоритета элемента в максимальной куче.^[2]^[3]

Чтобы вставить новый элемент в кучу, этот элемент добавляется в конец массива, а затем, когда свойство кучи нарушается, он заменяется местами своего родителя, перемещая его вверх по дереву и раньше в массиве, пока в конечном итоге не будет свойство кучи удовлетворено. Та же процедура перестановки вверх может использоваться для уменьшения приоритета элемента в минимальной куче или для увеличения приоритета элемента в максимальной куче. ^[2]^[3]

Чтобы создать новую кучу из массива из $n$ элементов, можно перебрать элементы в обратном порядке, начиная с элемента в позиции $n - 1$ и заканчивая элементом в позиции 0, применяя процедуру перестановки вниз для каждого элемента. ^[2]^[3]

Анализ [ править ]

В $d$ -ary куче, содержащей $n$ элементов, как процедура перестановки вверх, так и процедура перестановки вниз могут выполнять столько свопов, сколько $log d n = log n / log d$ . В процедуре перестановки снизу вверх каждая перестановка включает однократное сравнение элемента с его родительским элементом и занимает постоянное время. Следовательно, время для вставки нового элемента в кучу, уменьшения приоритета элемента в минимальной куче или увеличения приоритета элемента в максимальной куче составляет $O (log n / log d)$ . В процедуре перестановки вниз каждая перестановка включает $d$ сравнений и занимает $O (d)$ time: требуется $d - 1$ сравнений, чтобы определить минимум или максимум дочерних элементов, а затем еще одно сравнение с родительским, чтобы определить, требуется ли своп. Следовательно, время для удаления корневого элемента, увеличения приоритета элемента в минимальной куче или уменьшения приоритета элемента в максимальной куче составляет $O (d log n / log d)$ . ^[2]^[3]

При создании $d-$ кучи из набора из n элементов большинство элементов находятся в позициях, которые в конечном итоге будут содержать листья $d$ -ary дерева, и для этих элементов не выполняется перестановка вниз. Не более $n / d + 1$ элементов не являются листьями, и их можно поменять местами вниз по крайней мере один раз за время $O (d),$ чтобы найти потомка, чтобы поменять их местами. Максимум $n / d 2 + 1$ узлов может быть переключено вниз два раза, что потребует дополнительного $O (d)$ стоимость второго свопа сверх стоимости, уже учтенной в первом члене, и т. д. Таким образом, общее время создания кучи таким образом равно

{\ displaystyle \ sum _ {i = 1} ^ {\ log _ {d} n} \ left ({\ frac {n} {d ^ {i}}} + 1 \ right) O (d) = O ( n).}

^[2]^[3]

Известно, что точное значение вышеуказанного (наихудшее количество сравнений при построении d-арной кучи) равно:

{\ displaystyle {\ frac {d} {d-1}} (n-s_ {d} (n)) - (d-1- (n {\ bmod {d}})) \ left (e_ {d} \ left (\ left \ lfloor {\ frac {n} {d}} \ right \ rfloor \ right) +1 \ right)}

, ^[8]

где s _d (n) - сумма всех цифр стандартного представления n по основанию d, а e _d (n) - показатель степени d при факторизации n. Это сводится к

{\ displaystyle 2n-2s_ {2} (n) -e_ {2} (n)}

, ^[8]

для d = 2 и для

{\ displaystyle {\ frac {3} {2}} (n-s_ {3} (n)) - 2e_ {3} (n) -e_ {3} (n-1)}

, ^[8]

для d = 3.

Использование пространства $d -ary$ кучи с операциями insert и delete-min является линейным, поскольку не использует дополнительного хранилища, кроме массива, содержащего список элементов в куче. ^[2]^[7] Если необходимо поддерживать изменения приоритетов существующих элементов, то необходимо также поддерживать указатели с элементов на их позиции в куче, которая снова использует только линейное хранилище. ^[2]

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

При работе с графом с $m$ ребрами и $n$ вершинами как алгоритм Дейкстры для кратчайших путей, так и алгоритм Прима для минимальных остовных деревьев используют минимальную кучу, в которой есть $n$ операций удаления- минимума и до $m$ операций с пониженным приоритетом. Используя $d-$ мерную кучу с $d = m / n$ , общее время для этих двух типов операций может быть уравновешено друг с другом, что приведет к общему времени $O (m log m / n n)$ для алгоритма, улучшение по сравнению с временем работы $O (m log n)$ версий двоичной кучи этих алгоритмов всякий раз, когда количество ребер значительно превышает количество вершин. ^[1]^[5] Альтернативная структура данных очереди приоритетов, куча Фибоначчи , дает еще лучшее теоретическое время работы $O (m + n log n)$ , но на практике $d$ -ary кучи обычно работают не менее быстро, а часто быстрее, чем кучи Фибоначчи для этого приложения. ^[9]

На практике 4-кучи могут работать лучше, чем двоичные кучи, даже для операций удаления мин. ^[2]^[3] Кроме того, $d$ -ary куча обычно работает намного быстрее, чем двоичная куча для размеров кучи, которые превышают размер кэш-памяти компьютера : двоичная куча обычно требует больше промахов кеша и ошибок страниц виртуальной памяти, чем $d$ -ary heap, каждый из которых занимает гораздо больше времени, чем дополнительная работа, вызванная дополнительными сравнениями, которые выполняет $d$ -ary куча по сравнению с двоичной кучей. ^[6]^[10]

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

^ a b c d Джонсон, DB (1975), «Очереди приоритетов с обновлением и поиском минимальных остовных деревьев», Письма об обработке информации , 4 (3): 53–57, DOI : 10.1016 / 0020-0190 (75) 90001-0 CS1 maint: обескураженный параметр ( ссылка ).
^ a b c d e f g h i j k l Tarjan, RE (1983), "3.2. d -heaps", Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS-NSF по прикладной математике, 44 , Общество промышленного и Прикладная математика , стр. 34–38.. Обратите внимание, что Тарджан использует нумерацию на основе 1, а не на основе 0, поэтому его формулы для родительского и дочернего узла должны быть скорректированы при использовании нумерации на основе 0.
^ a b c d e f g h Вайс, Массачусетс (2007), " d -heaps", Структуры данных и анализ алгоритмов (2-е изд.), Addison-Wesley, p. 216, ISBN 0-321-37013-9.
^ Jensen, C .; Katajainen, J .; Витале, Ф. (2004), Расширенная правда о кучах (PDF) .
↑ a b Tarjan (1983) , стр. 77 и 91.
^ a b Naor, D .; Martel, CU; Matloff, NS (октябрь 1991), "Производительность структур очередей приоритетов в среде виртуальной памяти", Computer Journal , 34 (5): 428-437, DOI : 10,1093 / comjnl / 34.5.428.
^ a b Мортенсен, CW; Петти, С. (2005), "Сложность неявных и эффективных по пространству очередей приоритетов", Алгоритмы и структуры данных: 9-й международный семинар, WADS 2005, Ватерлоо, Канада, 15–17 августа 2005 г., Труды , конспекты лекций по информатике , 3608 ., Springer-Verlag, стр 49-60, DOI : 10.1007 / 11534273_6 , ISBN 978-3-540-28101-6.
^ Б с Suchenek Марек A. (2012), "Элементарные же Precise Наихудший анализ Heap-строительная программа Флойда" , Fundamenta Informaticae , IOS Press, 120 (1): 75-92, DOI : 10,3233 / FI- 2012-751.
^ Черкасский, Борис В .; Гольдберг, Эндрю В .; Radzik, Томаш (май 1996 г.), "кратчайших алгоритмы: теория и экспериментальная оценка" , Математическое программирование , 73 (2): 129-174, CiteSeerX 10.1.1.48.752 , DOI : 10.1007 / BF02592101 .
↑ Камп, Поул-Хеннинг (11 июня 2010 г.), «Вы делаете это неправильно» , очередь ACM , 8 (6).

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

Реализация обобщенной кучи на C ++ с поддержкой D-Heap

[j75-1] Джонсон, DB (1975), «Очереди приоритетов с обновлением и поиском минимальных остовных деревьев», Письма об обработке информации , 4 (3): 53–57, DOI : 10.1016 / 0020-0190 (75) 90001-0 CS1 maint: обескураженный параметр ( ссылка ).

[t83-2] ^ a b c d e f g h i j k l Tarjan, RE (1983), "3.2. d -heaps", Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS-NSF по прикладной математике, 44 , Общество промышленного и Прикладная математика , стр. 34–38.. Обратите внимание, что Тарджан использует нумерацию на основе 1, а не на основе 0, поэтому его формулы для родительского и дочернего узла должны быть скорректированы при использовании нумерации на основе 0.

[w07-3] Вайс, Массачусетс (2007), " d -heaps", Структуры данных и анализ алгоритмов (2-е изд.), Addison-Wesley, p. 216, ISBN 0-321-37013-9.

[4] Jensen, C .; Katajainen, J .; Витале, Ф. (2004), Расширенная правда о кучах (PDF) .

[t2-5] Tarjan (1983) , стр. 77 и 91.

[nmm91-6] Naor, D .; Martel, CU; Matloff, NS (октябрь 1991), "Производительность структур очередей приоритетов в среде виртуальной памяти", Computer Journal , 34 (5): 428-437, DOI : 10,1093 / comjnl / 34.5.428.

[mp05-7] Мортенсен, CW; Петти, С. (2005), "Сложность неявных и эффективных по пространству очередей приоритетов", Алгоритмы и структуры данных: 9-й международный семинар, WADS 2005, Ватерлоо, Канада, 15–17 августа 2005 г., Труды , конспекты лекций по информатике , 3608 ., Springer-Verlag, стр 49-60, DOI : 10.1007 / 11534273_6 , ISBN 978-3-540-28101-6.

[Suchenek-8] Б с Suchenek Марек A. (2012), "Элементарные же Precise Наихудший анализ Heap-строительная программа Флойда" , Fundamenta Informaticae , IOS Press, 120 (1): 75-92, DOI : 10,3233 / FI- 2012-751.

[9] Черкасский, Борис В .; Гольдберг, Эндрю В .; Radzik, Томаш (май 1996 г.), "кратчайших алгоритмы: теория и экспериментальная оценка" , Математическое программирование , 73 (2): 129-174, CiteSeerX 10.1.1.48.752 , DOI : 10.1007 / BF02592101 .

[k10-10] Камп, Поул-Хеннинг (11 июня 2010 г.), «Вы делаете это неправильно» , очередь ACM , 8 (6).

[1]