d -арная куча

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

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

Структура данных

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

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

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

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

Анализ

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

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

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

^[2]^[3]

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

{\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, а ed ₍ n) — показатель степени d при факторизации n. Это сводится к

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

, ^[8]

для d = 2 и

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

, ^[8]

для d = 3.

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

Приложения

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д Джонсон, Д.Б. (1975), «Приоритетные очереди с обновлением и поиском минимальных связующих деревьев», Information Processing Letters , 4 (3): 53–57, doi : 10.1016/0020-0190(75)90001-0 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Тарьян, Р.Э. (1983), «3.2.d - кучи», Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS-NSF по прикладной математике, том. 44, Общество промышленной и прикладной математики , стр. 34–38 . Обратите внимание, что Тарьян использует нумерацию с отсчетом от 1, а не от 0, поэтому его формулы для родительского и дочернего узла необходимо корректировать, когда используется нумерация с отсчетом от 0.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Вайс, Массачусетс (2007), « d -кучи», Структуры данных и анализ алгоритмов (2-е изд.), Аддисон-Уэсли, стр. 216, ISBN 978-0-321-37013-6 .
^ Дженсен, К.; Катахайнен, Дж.; Витале, Ф. (2004), Расширенная правда о кучах (PDF) , заархивировано из оригинала (PDF) 9 июня 2007 г. , получено 5 февраля 2008 г.
^ Jump up to: ^а ^б Тарьян (1983) , стр. 77 и 91.
^ Jump up to: ^а ^б Наор, Д.; Мартель, CU; Матлофф, Н.С. (октябрь 1991 г.), «Производительность структур очередей с приоритетами в среде виртуальной памяти», Computer Journal , 34 (5): 428–437, doi : 10.1093/comjnl/34.5.428 .
^ Jump up to: ^а ^б Мортенсен, CW; Петти, С. (2005), «Сложность неявных и эффективных с точки зрения использования пространства очередей приоритетов», Алгоритмы и структуры данных: 9-й международный семинар, WADS 2005, Ватерлоо, Канада, 15–17 августа 2005 г., Труды , Конспекты лекций по информатике , том. 3608, Springer-Verlag, стр. 49–60, номер документа : 10.1007/11534273_6 , ISBN. 978-3-540-28101-6 .
^ Jump up to: ^а ^б ^с Сученек, Марек А. (2012), «Элементарный, но точный анализ наихудшего случая программы Флойда по построению кучи» , Fundamenta Informaticae , 120 (1), IOS Press: 75–92, doi : 10.3233/FI-2012-751 .
^ Черкасский Борис Владимирович; Гольдберг, Эндрю В .; Радзик, Томаш (май 1996 г.), «Алгоритмы кратчайших путей: теория и экспериментальная оценка» , Mathematical Programming , 73 (2): 129–174, CiteSeerX 10.1.1.48.752 , doi : 10.1007/BF02592101 .
^ Камп, Пол-Хеннинг (11 июня 2010 г.), «Вы делаете это неправильно» , ACM Queue , 8 (6) .

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

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

[j75-1] Jump up to: ^а ^б ^с ^д Джонсон, Д.Б. (1975), «Приоритетные очереди с обновлением и поиском минимальных связующих деревьев», Information Processing Letters , 4 (3): 53–57, doi : 10.1016/0020-0190(75)90001-0 .

[t83-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Тарьян, Р.Э. (1983), «3.2.d - кучи», Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS-NSF по прикладной математике, том. 44, Общество промышленной и прикладной математики , стр. 34–38 . Обратите внимание, что Тарьян использует нумерацию с отсчетом от 1, а не от 0, поэтому его формулы для родительского и дочернего узла необходимо корректировать, когда используется нумерация с отсчетом от 0.

[w07-3] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Вайс, Массачусетс (2007), « d -кучи», Структуры данных и анализ алгоритмов (2-е изд.), Аддисон-Уэсли, стр. 216, ISBN 978-0-321-37013-6 .

[4] Дженсен, К.; Катахайнен, Дж.; Витале, Ф. (2004), Расширенная правда о кучах (PDF) , заархивировано из оригинала (PDF) 9 июня 2007 г. , получено 5 февраля 2008 г.

[t2-5] Jump up to: ^а ^б Тарьян (1983) , стр. 77 и 91.

[nmm91-6] Jump up to: ^а ^б Наор, Д.; Мартель, CU; Матлофф, Н.С. (октябрь 1991 г.), «Производительность структур очередей с приоритетами в среде виртуальной памяти», Computer Journal , 34 (5): 428–437, doi : 10.1093/comjnl/34.5.428 .

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

[Suchenek-8] Jump up to: ^а ^б ^с Сученек, Марек А. (2012), «Элементарный, но точный анализ наихудшего случая программы Флойда по построению кучи» , Fundamenta Informaticae , 120 (1), IOS Press: 75–92, doi : 10.3233/FI-2012-751 .

[9] Черкасский Борис Владимирович; Гольдберг, Эндрю В .; Радзик, Томаш (май 1996 г.), «Алгоритмы кратчайших путей: теория и экспериментальная оценка» , Mathematical Programming , 73 (2): 129–174, CiteSeerX 10.1.1.48.752 , doi : 10.1007/BF02592101 .

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]