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$ через $di + d$ . Согласно свойству кучи , в минимальной куче каждый элемент имеет приоритет, который по крайней мере такой же большой, как у его родителя; в максимальной куче каждый элемент имеет приоритет, который не больше, чем у его родителя. ^[2]^[3]

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

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

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

Анализ

В $d$ -арной куче, содержащей $n$ элементов, как процедура восходящей перестановки, так и процедура нисходящей перестановки могут выполнять до $log d n = log n / log d$ перестановок. В процедуре восходящей перестановки каждая перестановка включает в себя одно сравнение элемента с его родителем и занимает постоянное время. Таким образом, время вставки нового элемента в кучу, уменьшения приоритета элемента в min-куче или увеличения приоритета элемента в max-куче составляет $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)$ времени на поиск дочернего элемента, с которым их можно поменять местами. Максимум $n / 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, а e _d (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$ операций удаления минимума и до $m$ операций понижения приоритета. Используя $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$ -арная куча обычно работает намного быстрее, чем двоичная куча, для размеров кучи, которые превышают размер кэш -памяти компьютера ; ^[10] это может быть связано с тем, что двоичная куча подразумевает больше промахов кэша или ошибок страниц виртуальной памяти , которые могут потреблять больше времени обработки, чем дополнительная работа нескольких дополнительных сравнений на каждом уровне, подразумеваемых $d$ -арной кучей. ^[6]^[11]

Ссылки

^ abcd Джонсон, ДБ (1975), «Приоритетные очереди с обновлением и поиском минимальных остовных деревьев», Information Processing Letters , 4 (3): 53–57, doi :10.1016/0020-0190(75)90001-0.
^ abcdefghijkl Tarjan, RE (1983), "3.2. d -heaps", Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS-NSF по прикладной математике, т. 44, Общество промышленной и прикладной математики , стр. 34–38. Обратите внимание, что Тарьян использует нумерацию, начинающуюся с 1, а не с 0, поэтому его формулы для родительских и дочерних элементов узла необходимо скорректировать при использовании нумерации, начинающейся с 0.
^ abcdefgh Weiss, MA (2007), " d -heaps", Data Structures and Algorithm Analysis (2-е изд.), Addison-Wesley, стр. 216, ISBN 978-0-321-37013-6.
^ Йенсен, К.; Катаяйнен, Дж.; Витале, Ф. (2004), Расширенная правда о кучах (PDF) , заархивировано из оригинала (PDF) 2007-06-09 , извлечено 2008-02-05.
^ аб Тарьян (1983), стр. 77 и 91.
^ ab Naor, D.; Martel, CU; Matloff, NS (октябрь 1991 г.), «Производительность структур приоритетной очереди в среде виртуальной памяти», Computer Journal , 34 (5): 428–437, doi : 10.1093/comjnl/34.5.428.
^ ab Мортенсен, CW; Петти, S. (2005), "Сложность неявных и эффективных по пространству приоритетных очередей", Алгоритмы и структуры данных: 9-й международный семинар, WADS 2005, Ватерлоо, Канада, 15–17 августа 2005 г., Труды , Заметки лекций по информатике, т. 3608, Springer-Verlag, стр. 49–60, doi :10.1007/11534273_6, ISBN 978-3-540-28101-6.
^ abc Suchenek, Marek A. (2012), «Элементарный, но точный анализ наихудшего случая программы построения кучи Флойда», Fundamenta Informaticae , 120 (1), IOS Press: 75–92, doi :10.3233/FI-2012-751.
^ Черкасский, Борис В.; Голдберг, Эндрю В.; Радзик, Томаш (май 1996), «Алгоритмы кратчайших путей: теория и экспериментальная оценка», Математическое программирование , 73 (2): 129–174, CiteSeerX 10.1.1.48.752 , doi :10.1007/BF02592101
^ Ларкин, Дэниел; Сен, Сиддхартха; Тарьян, Роберт (2014). «Возвращение к основам эмпирического исследования приоритетных очередей». Труды шестнадцатого семинара по разработке алгоритмов и экспериментам : 61–72. arXiv : 1403.0252 . Bibcode : 2014arXiv1403.0252L. doi : 10.1137/1.9781611973198.7. ISBN 978-1-61197-319-8. S2CID 15216766.
^ Камп, Поул-Хеннинг (11 июня 2010 г.), «Вы делаете это неправильно», ACM Queue , 8 (6).

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

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